Postfix to Infix Conversion Algorithm, example and program

In this tutorial We have explored an algorithm to convert a given Postfix expression to Infix expression using Stack.

Algorithm For Postfix to Infix Conversion

Iterate the given expression from left to right, one character at a time 
 Step 1 : If a character is operand, push it to stack.
 Step 2: If a character is an operator, 
     if there are fewer than 2 values on the stack
         give error "insufficient values in expression" goto Step 4
     else
         pop 2 operands from stack 
         create a new string and by putting the operator between operands.
         push this string into stack
     Repeat Steps 1 and 2
 Step 3: At last there will be only one value or one string in the stack which will be our infix expression
 Step 4: Exit

Some important terminology

Postfix Expression
In Postfix Expression operator appear after operand, this expression is known as Postfix operation.
Infix
If Infix Expression operator is in between of operands, this expression is known as Infix operation.

Steps to Convert Postfix to Infix

• Start Iterating the given Postfix Expression from Left to right
• If Character is operand then push it into the stack.
• If Character is operator then pop top 2 Characters which is operands from the stack.
• After poping create a string in which comming operator will be in between the operands.
• push this newly created string into stack.
• Above process will continue till expression have characters left
• At the end only one value will remain if there is integers in expressions. If there is character then one string will be in output as infix expression.

Example to convert postfix to Infix

Postfix Expression : abc-+de-+

Token	Stack	Action
a	a	push a in stack
b	a, b	push b in stack
c	a, b, c	push c in stack
–	a , b – c	pop b and c from stack and put – in between and push into stack
+	a + b – c	pop a and b-c from stack and put + in between and push into stack
d	a + b – c, d	push d in stack
e	a + b – c, d , e	push e in stack
–	a + b – c, d – e	pop d and e from stack and put – in between and push into stack
+	a + b – c + d – e	pop a + b – c and d – e from stack and put + in between and push into stack

Solution for postfix expression

postfix expression: 752+*415-/-

Token	Stack	Action
7	7	push 7 in stack
5	7, 5	push 5 in stack
2	7 , 5, 2	push 2 in stack
+	7, 7	pop 2 and 5 from stack, sum it and then again push it
*	49	pop 7 and 7 from stack and multiply it and then push it again
4	49, 4	push 4 in stack
1	49, 4, 1	push 1 in stack
5	49, 4, 1, 5	push 5 in stack
–	49, 4, -4	pop 5 and 1 from stack
/	49, -1	pop 4 and 4 from stack
–	50	pop 1 and 49 from stack

Infix to postfix conversion program

import java.util.*;

public class Main {

    public static String convert(String exp){
        int len = exp.length();
        Stack<String> stack = new Stack<>();
        for (int i = 0; i <len ; i++) {
            char c = exp.charAt(i);

            if(c=='*'||c=='/'||c=='^'||c=='+'||c=='-' ){
                String s1 = stack.pop();
                String s2 = stack.pop();
                String temp = "("+s2+c+s1+")";
                stack.push(temp);
            }else{
                stack.push(c+"");
            }
        }

        String result=stack.pop();
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter Postfix Expression: ");
        String exp = sc.nextLine();
        System.out.println("Infix Expression: " + Main.convert(exp));
    }
}

---

[wpusb]