In this article, we will continue with another problem related to application of Stack Data Structure. Given a Postfix Expression we have to convert into its Equivalent Infix Expression.
It is recommended to first learn Infix to postfix conversion before proceeding with this.
Now, let us have a quick recap. Infix Expressions are expressions where operators are written between every pair of operands and are of the form : x op y . Postfix Expressions are mathematical expressions where an operator is followed for every pair of operands and are of form : a b op . op is the operator, a and b are operands.
For Example: For the Postfix Expression: ABC-* , The Equivalent Infix will be A*(B - C).
Algorithm for Postfix to Infix in Java
- We traverse the given Postfix expression from left to right. We will use a single stack Infix which stores operands and at the end will hold our resultant Infix Expression.
- For each character, we will take two decisions:
- If the Character is a Operand we push it into Infix Stack.
- If the Character is a Operator, we pop two elements from the Stack, add last element with the operator and concatenate it with the first element and push the result back to the Infix Stack again for future evaluation.
- At the time of adding a part of evaluated expression we enclose them within Parentheses to determine the order of operations.
- When we traverse the whole string at the end, we will be left with only one value in our stack, which will be our Infix Expression.
Let us understand this with an example. Consider the Postfix expression : ABC- * D / .
Let us evaluate the given expression. We take decisions when we encounter Operator or Operands. The steps are:
-
Step 1:We start iterating through each character (ignoring the spaces). At i=0, char = ‘A’ an Operand. We push it into Infix stack. At i=1 and i=2 char = ‘B’ and ‘C’ respectively, we push them into Infix stack. The stack looks like:
-
Step 2:We continue, at i=3, char = ‘-‘ , an Operator we follow Step 2 Case 2, pop two elements from stack and add them with operator , we enclose the total expression within parentheses. Then, push the result back into stack. The stack now is :
Now, (B-C) is an Operand . -
Step 3:At i=4, we get char = ‘*’, an operator . So we repeat the above step and the Infix stack is now:
-
Step 4:At i=5, we get char = ‘D’ an operand we push it into stack.
-
Step 5:Finally at i=6, char =’/’, we perform Step 2 again by popping the two remaining elements and the Infix stack now is :
The Infix stack at last contains our resultant infix Expression which is : (( A * (B - C)) / D).
Implementation for Postfix to Infix in Java
Let us now look at the implementation of above 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 |
import java.util.*; class PostfixToInfix { static boolean isOperand(char ch) { // we check for uppercase and lowercase alphabets. if(ch >= 'a' && ch <= 'z') return true; else if(ch >= 'A' && ch <= 'Z') return true; return false; // if not an Operand return false; } // converts postfix to infix and returns the expression static String convertToInfix(String postfix) { Stack<String> inFix = new Stack<>(); for (int i = 0; i < postfix.length(); i++) { char ch = postfix.charAt(i); if (isOperand(ch)) { // Push operands to stack. inFix.push(ch + ""); } // Step 2: Evaluate part of the expression and push it again to stack. else { String op1 = inFix.pop(); String op2 = inFix.pop(); inFix.push("(" + op2 + ch + op1 + ")"); } } return inFix.pop(); } public static void main(String args[]) { String postfix = "ABC-*D/"; System.out.println("The Postfix Expression is: "+ postfix); String result = convertToInfix(postfix); System.out.println("The Infix Expression is : "+result); } } |
Output:
|
1 2 3 4 |
The Postfix Expression is: ABC-*D/ The Infix Expression is : ((A*(B-C))/D) |
Let us look at the Time Complexity for this code. The time complexity is O(n), where n is the length of Postfix Expression.
So that’s all about Convert Postfix to Infix in Java. You can try out this code with different examples.
