In this article we continue with another interesting problem related to Stack data structure. Given a Prefix expression, convert into its Equivalent Postfix Expression.
Table of Contents
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
- 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.
- For each character we encounter, we consider two cases:
- f the Character is a Operand we push it into the Postfix Stack.
- 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.
- 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. Ati=6, we have char = ‘D’, an operand so we push it into the Postfix Stack. Ati=5, we have char = ‘C’, we push it into the stack. The Postfix stack now is:
-
Step 2:We continue iteration ati=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 ati=3, we have char = ‘B’, and ati=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:Ati=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 Ati=0, we get char =’/’, an Operator so we pop both the operands (AB+andCD-) 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import java.util.*; class PrefixToPostfix { // check if character is operator or not static boolean isOperator(char ch) { if(ch == '+' || ch == '-' || ch == '*' || ch == '/') return true; return false; } // Convert prefix to Postfix expression static String convertPrefixToPostfix(String prefix) { Stack<String> postFix = new Stack<>(); // length of prefix expression int n = prefix.length(); // reading from right to left for (int i = n - 1; i >= 0; i--) { char ch= prefix.charAt(i); // check if symbol is operator if (isOperator(ch)) { // pop two operands from stack String first = postFix.pop(); String second = postFix.pop(); // concat the operands and operator to form Postfix String temp_postFix = first + second + ch; // Push the partly evaluated postfix back to stack postFix.push(temp_postFix); } // if symbol is an operand else { // push the operand to the stack postFix.push(ch + ""); } } // stack contains only the Postfix expression return postFix.pop(); } public static void main(String args[]) { String prefix = "/+AB-CD"; // Infix is : (A+B) / (C-D). System.out.println("The Prefix Expression is: "+prefix); String result = convertPrefixToPostfix(prefix); System.out.println("The Equivalent Postfix is : "+ result); System.out.println(); prefix = "*+AB/-CDE"; // Infix is : (A+B) * ((C-D)/E). System.out.println("The Prefix Expression is: "+prefix); result = convertPrefixToPostfix(prefix); System.out.println("The Equivalent Postfix is : "+ result); } } |
Output:
|
1 2 3 4 5 6 7 |
The Prefix Expression is: /+AB-CD The Equivalent Postfix is : AB+CD-/ The Prefix Expression is: *+AB/-CDE The Equivalent Postfix is : AB+CD-E/* |
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.
