Home » Interview Questions » Stack Interview Questions » Postfix to Infix Conversion

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.

Postfix to Infix Conversion

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.

READ  Print Next Greater Number of Q queries

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

References

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions