Convert Postfix to Infix

Problem Statement:

Given an infix expression, convert into postfix expression.

Infix expression: a op b

Postfix expression: a b op

Solution

In this solution we shall use stack data structure.

Below are the steps:

1. Start from left to right

2. If the char is a operand (value), then push into the stack

else

3. If the char is an operator, then pop 2 elements from stack

4. Then put the operator with the values as arguments and generate a string.

5. Push the result string back to stack.

At the end there will be one value in stack, that will be the result.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;

bool isOperand(char x) 
{ 
   return (x >= 'a' && x <= 'z') || 
          (x >= 'A' && x <= 'Z') ||
          (x >= '0' && x <= '9') ; 
} 
  

string postfix_to_infix(string exp) 
{ 
    stack<string> s; 
  
    for (int i=0; exp[i]!='\0'; i++) 
    { 
        // check if char is a value and push it
        if (isOperand(exp[i])) 
        { 
           string op(1, exp[i]); 
           s.push(op); 
        } 
  
        else
        { 
            string op1 = s.top(); 
            s.pop(); 
            string op2 = s.top(); 
            s.pop(); 
            s.push("(" + op2 + exp[i] + 
                   op1 + ")"); 
        } 
    } 

    return s.top(); 
} 
  
int main() 
{ 
    string exp = "12*3+"; 
    cout << postfix_to_infix(exp); 
    return 0; 
} 

Output:

((1*2)+3)