Postfix to Infix

We can convert any postfix expression to infix expression using stack in one pass.

Example

Input: abc^d/e*+
Output: (a+(((b^c)/d)*e))

Postfix to Infix Algorithm

Steps

1. Initialize an empty stack.
2. Scan postfix expression from left to right.
   1. If the scanned character is an operand, push it to the stack.
   2. If the scanned character is an operator,
      1. Pop the operands.
      2. Insert operator between operands and form a string.
      3. Insert “(“, “)” at the beginning and end of the string.
      4. Insert this string to stack.
3. Repeat step 2 until are characters are read.
4. The final string in the stack is the infix expression.

Example,

Convert “abc^d/e*+” to Infix.

Pseudo code

postfix: stores the input postfix expression
token: stores character of postfix for each iteration 
FOR i = 0 to postfix.LENGTH DO
	token = postfix[i]
	IF token is operand THEN
		PUSH token to stack
	ELSE IF token is operator THEN
		POP operands from stack
		Insert token between them and form a string
		Encapsulate string in "(" and ")"
		PUSH the string to stack
	END
END FOR

Code

#include<iostream>
#include<string>
#include<stack>
using namespace std;

bool isOperator(string t) {
	if(t=="+"||t=="-"||t=="/"||t=="*"||t=="^")	return true;
	return false;
}

bool isOperand(string t){
	if(t>="a"&&t<="z")	return true;
	return false;
}

string convertPostfixToInfix(string postfix){
	stack<string> stk;
	string token;
	for(int i=0;i<postfix.length();++i){
		token = postfix[i];
		if(isOperand(token)){
			stk.push(token);
		}
		else if(isOperator(token)){
			// since we are only using binary operators
			// we can pop values without checking for the operators
			// but if your postfix contains unary,tarnary,.. operators
			// then we need to check what type of operator it is
			// and then pop the stack
			string p1 = stk.top();
			stk.pop();
			string p2 = stk.top();
			stk.pop();
			stk.push("("+p2+token+p1+")");
		}
	}
	return stk.top();
}

int main() {
	// it stores infix expression
	string postfix,infix;
	cout << "Enter Postfix Expression: ";
	cin >> postfix;
	infix = convertPostfixToInfix(postfix);
	cout<<"Infix Expression is: "<<infix<<endl;
}

Output

Enter Postfix Expression: abc^d/e*+
Infix Expression is: (a+(((b^c)/d)*e))

Time Complexity of Postfix to Infix conversion

Let N be the length of input postfix expression.
We are iterating each character of postfix once but in each iteration, we are also performing string manipulation which again takes time O(N).
Thus, the complexity of the algorithm is O(N²)

References

https://en.wikipedia.org/wiki/Shunting-yard_algorithm