# 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(N2)

## References

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