Postfix to Infix Conversion

In postfix to infix conversion problem, we have given expression in postfix notation. Write a program to convert the given notation in infix notation.

Infix Notation

In this notation, the operators are written between the operands. It is similar to how we generally write an expression.

For instance: A + B is an infix expression.

Postfix Notation

In this notation, the operands are written before the operator. It is also known as Reverse Polish Notation.

For instance: AB+ is a postfix expression.

Given an expression in postfix notation. Write a program to convert the given notation in infix notation.

Example

Input : Postfix : ABC/-AD/E-*

Output : Infix : ((A-(B/C))*((A/D)-E))

Input : Postfix : AB+CD-*

Output : Infix : ((A+B)*(C-D))

Algorithm for Postfix to Infix Conversion

1. Initialize a string containing postfix expression.
2. Create a stack s of type string.
3. Traverse from the start to end of the string and check if the current character is an operand push it as a string in the stack.
4. Else pop the two top characters from the stack and concatenate them as SECOND CHARACTER + CURRENT OPERATOR + FIRST CHARACTER. Push the string back into the stack.
5. Return the top of the stack.

Implementation for Postfix to Infix Conversion

C++ Program

#include <bits/stdc++.h> 
using namespace std; 
  
bool isOperand(char x){ 
   return((x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z')); 
} 
  
string postfixToInfix(string postfix_exp){ 
    stack<string> s; 
  
    for(int i=0; postfix_exp[i]!='\0'; i++){ 

        if(isOperand(postfix_exp[i])){ 
           string op(1, postfix_exp[i]); 
           s.push(op); 
        } 
  
        else{ 
            string op1 = s.top(); 
            s.pop(); 
            string op2 = s.top(); 
            s.pop(); 
            s.push("(" + op2 + postfix_exp[i] + op1 + ")"); 
        } 
    } 
    return s.top(); 
} 
int main(){
    string postfix_exp = "ABC/-AD/E-*"; 
    cout<<"Infix : "<<postfixToInfix(postfix_exp); 
    return 0; 
}

Infix : ((A-(B/C))*((A/D)-E))

Java Program

import java.util.*; 
class Postfix{      
    static boolean isOperand(char x)
    { 
      return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'); 
    }       
    static String postfixToInfix(String postfix_exp){ 
        Stack<String> s = new Stack<String>(); 
        for(int i = 0; i<postfix_exp.length(); i++)
        { 
            if(isOperand(postfix_exp.charAt(i))){ 
                s.push(postfix_exp.charAt(i) + ""); 
            }      
            else
            { 
                String op1 = s.peek(); 
                s.pop(); 
                String op2 = s.peek(); 
                s.pop(); 
                s.push("(" + op2 + postfix_exp.charAt(i) + op1 + ")"); 
            } 
        }       
        return s.peek(); 
    }       
    public static void main(String args[]){        
        String postfix_exp = "ABC/-AD/E-*";
        System.out.println("Infix : "+postfixToInfix(postfix_exp));       
    } 
}

Infix : ((A-(B/C))*((A/D)-E))

Complexity Analysis for Postfix to Infix Conversion

Time Complexity: O(n) where n is the length of the postfix string.

Space Complexity: O(n) as we use space to store each of the n characters of the string.

References