Convert Prefix to Postfix in Java

Prefix to postfix in java

In this article we continue with another interesting problem related to Stack data structure. Given a Prefix expression, convert into its Equivalent Postfix Expression.

It is recommended to first go through Infix to postfix conversion for better understanding.

Let us understand what we mean by Prefix and Postfix Expression.

Prefix Expression is an expression where operators precede the operands. In simpler terms, the operators appear before the operands in the expression. They are of form : op X Y, op is operator and X,Y are operands. For Example: +AB is a Prefix Expression for Infix: A+B.

Postfix Expressions re of the form X Y op, where operators come after operands. For Example: AB+ is the Postfix for Infix: A+B.

We need to convert Prefix to Postfix so for the Prefix Expression : + / AB * CD , the Infix will be : (A / B) + (C * D). Then on converting this infix the resultant Postfix Expression will be : AB/ CD* + .

Now, to convert Prefix expression into Postfix, we can try first converting the Prefix into Infix notation then convert the result into Postfix. But, we can do this in a single step by directly converting the Prefix into Postfix. Let us look at the Algorithm.

Algorithm for prefix to postfix

  1. We will start traversing the Prefix Expression from Right to Left, unlike what we did in Infix to Postfix Conversion. We will use a single Stack Postfix which will hold the operands and a part of evaluated Postfix expression. When we reach the end ( at i = -1) , the stack will hold the resultant Postfix expression.
  2. For each character we encounter, we consider two cases:
    1. f the Character is a Operand we push it into the Postfix Stack.
    2. If the Character is a Operator we pop two elements from the Stack, add two elements together followed with the operator and push the result back to the Postfix Stack again for future evaluation. This will be the part of total Postfix.
  3. When we come to end of the String traversing from Right (Length-1) to Left (0) , at i=-1 we stop and at the at the end the Postfix stack contain only one value, which will be the resultant Postfix Expression.

Now, let us understand this algorithm with an example. Consider the Prefix expression : /+AB-CD. The Infix for this is : ((A + B) / (C – D)).

Let us evaluate the given expression step by step. We take decisions when we encounter Operator or Operands. The steps are:

  • Step 1: We start iterating from the end of the string (length – 1 = 7 – 1 = 6 ) to start index. At i=6, we have char = ‘D’, an operand so we push it into the Postfix Stack. At i=5, we have char = ‘C’, we push it into the stack. The Postfix stack now is:

  • Step 2: We continue iteration at i=4, char = ‘-‘ , an operator, so we pop two operands from stack and add them with the operator in the same order. We then push the result (CD-) into the Postfix stack again for future evaluation. The stack now is:

    Now, CD- is an Operand.
  • Step 3: Now at i=3, we have char = ‘B’, and at i=2, we have char = ‘A’, since both are operands so we push them into stack one by one . The Postfix stack is now:

  • Step 4: At i=1, char = ‘+’, an Operator. So we perform Step 2 again by popping and adding the two elements with the operator and then push the result (AB+) back to stack. The Postfix stack now looks :

  • Step 5: Finally At i=0, we get char =’/’, an Operator so we pop both the operands (AB+ and CD-) and add it with the operator. We stop iteration as we reached index 0. The Postfix stack at the end now contains our resultant Postfix Expression which is :

    The Postfix is: AB+ CD- /

Implementation for Prefix to postfix conversion in java

Let us look at the implementation of the above example in JAVA:

Output:

We have implemented two examples. Now let us look at the Time Complexity of our approach.

Time complexity

Time Complexity: As we traverse the whole input string once and the stack operations require constant time, the overall time complexity is O(n), n is the length of Prefix Expression.

So that’s all about how to convert Prefix to postfix in java. You can try with different examples and execute this code for better understanding.

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *