We will study how we can convert infix expression to postfix expression using stack.

**Infix Expression**

Infix Expression is in the form of **Operand Operator Operand**.

For example, **4 + 5**.

**Postfix Expression** ( or Reverse Polish Notation )

Postfix Expression is in form ** Operand Operand Operator**.

For example,

**4 5 +**.

**Why do we convert infix expression to postfix expression?**

1. Postfix expression lacks parenthesis. Thus, we do not have to worry about associativity and precedence of operators while evaluating the expression.

2. The expression can be easily solved using one stack. Evaluation of equivalent infix without converting it to postfix can be complex.

Before moving ahead we must know these terms:

**Precedence:**Precedence means which operator should be performed first. For example, if you have an expression**a+b*c**, then we will first multiple b and c and then add the result to a. This is because**“*”**has higher precedence than**“+”**. The expression**a+b*c**is performed as**(a+(b*c))**instead of**((a+b)*c)**.**Left-associativity:**A operator is said to be left-associative if, in absence of parenthesis, the operations are grouped from left to right.

For example, 2-1-1 is calculated as ((2-1)-1) = 0 and not as (2-(1-1)) = 2.

Subtraction and division are inherently left-associative.**Right-associativity:**A operator is said to be right-associative if, in absence of parenthesis, the operations are grouped from right to left.

For example, 2^3^2 is calculated as (2^(3^2)) = (2^9) = 512 not as ((2^3)^2) = (8^2) = 64.

Exponential operator (“^”) is inherently right-associative.

**Note: **Multiplication and addition are both left-associative and right-associative.

## Infix to Postfix Algorithm

We will study 2 methods

- The first method will include left-associative operators like
**+,-,*,/**. - The second method will include both left-associative and right-associative operators.

### Infix to Postfix first Approach (only for left-associative operators)

#### Steps

- Insert
**“(“**and**“)”**at the start and end of infix expression respectively. - Initialize a
**stack**, we call it**operator stack**. - Initialize a
**list**with name**prefix**. - Scan
**infix expression**from left to right.- If the
**scanned character**is an**operand,**then push it to the**postfix**. - If the
**scanned character**is “(“, then push it to the**stack**. - If the
**scanned character**is an**operator**, then keep popping the operators from the**stack**and push them to**postfix**till the**precedence**of the operator on top of the**stack**is greater than or equals to the**scanned character**. If we encounter**“(“**or the**precedence**of the operator on the**stack**is less than**scanned character**, push the**scanned character**to**postfix**. - If the
**scanned character**is**“)”**, keep popping operators from**operator stack**and push them till we encounter**“(“**and then pop the remaining**“(“**.

- If the
- Keep repeating steps 4 until all input characters are read.
- The postfix expression will be saved in
**postfix**.

Before moving to code, we will convert an infix expression “**a+b*(c/d*e)-f-g”** to prefix expression using the above algorithm.

First add “(” and “)” to ending and beginning of the infix expression.

Operator | Precedence |
---|---|

+,- | 1 |

*,/ | 2 |

Infix Expression | Operator Stack | Postfix Expression | Description |
---|---|---|---|

(a+b*(c/d*e)-f-g) | ( | Push “(” to stack. | |

a+b*(c/d*e)-f-g) | ( | a | Push a to postfix. |

+b*(c/d*e)-f-g) | (+ | a | Top of the stack is “(“. Push “+” to stack. |

b*(c/d*e)-f-g) | (+ | a,b | Push b to postfix. |

*(c/d*e)-f-g) | (+* | a,b | Since “+” have lower precedence than “*”, we do not pop the stack. Push “*” to stack. |

(c/d*e)-f-g) | (+*( | a,b | Push “(” to stack. |

/d*e)-f-g)c | (+*( | a,b,c | Push c to postfix. |

d*e)-f-g)/ | (+*(/ | a,b,c | Top of the stack is “(“. Push “/” to stack. |

d*e)-f-g) | (+*(/ | a,b,c,d | Push d to postfix. |

*e)-f-g) | (+*(* | a,b,c,d,/ | “/” have precedence greater equal to “*” Pop “/” from stack to postfix. Push “*” to stack. |

e)-f-g) | (+*(* | a,b,c,d,/,e | Push e to postfix. |

-f-g)) | (+* | a,b,c,d,/,e,* | Keep popping operators from stack to prefix till we encounter “(“. Pop “(” from the stack. |

–f-g) | (- | a,b,c,d,/,e,*,*,+ | “*”, “+” have precedence greater than equal to “-“. Pop “*” from stack to postfix. Pop “+” from stack to postfix. Push “-” to stack. |

f-g) | (- | a,b,c,d,/,e,*,*,+,f | Push f to postfix. |

–g) | (- | a,b,c,d,/,e,*,*,+,f,- | “-” have precedence greater than equal to “-“. Pop “-” from stack to postfix. Push “-” to stack. |

g) | (- | a,b,c,d,/,e,*,*,+,f,-,g | Push g to postfix. |

) | a,b,c,d,/,e,*,*,+,f,-,g,- | Keep popping elements from stack to prefix till we encounter “(“. Pop “(” from the stack. |

#### Pseudo Code

```
postfix: it stores the final postfix expression
opStack: it is used to store parenthesis and operators
infix: it stores the input infix expression
token: it stores infix character for each iteration
PUSH "(" AT BEGINNING OF infix
PUSH ")" AT END OF infix
FOR i = 1 to infix.LENGTH DO
token := infix[i]
IF token is "(" THEN
PUSH token IN opStack
ELSE IF token is operand THEN
PUSH token IN postfix
ELSE IF token is operator THEN
WHILE opStack.TOP is operator AND opStack.TOP Precedence >= token Precedence THEN
temp := opStack.TOP
opStack.POP
PUSH temp IN postfix
END WHILE
PUSH token IN opStack
ELSE if token == ")" THEN
WHILE opStack.TOP != "(" THEN
temp := opStack.TOP
opStack.POP
PUSH temp IN postfix
END WHILE
opStack.POP
END ELIF
END FOR
```

#### Code

```
#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool isOperand(char t) {
if (t >= 'a' && t <= 'z') return true;
else return false;
}
bool isOperator(char t) {
switch (t) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
// returns operator precedence
int prece(char t) {
if (t == '+' || t == '-') return 1;
if (t == '*' || t == '/') return 2;
return 0;
}
string convertInfixTopostfix(string infix) {
// operator stack
stack<char> opStack;
// it stores final postfix expression
string postfix;
// it stores each token of infix expression
char token;
postfix = "";
for (int i = 0; i < infix.length(); ++i) {
token = infix[i];
if (token == '(') {
opStack.push(token);
}
else if (isOperand(token)) {
postfix.push_back(token);
}
else if (isOperator(token)) {
while (isOperator(opStack.top()) && (prece(opStack.top()) >= prece(token))) {
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
opStack.push(token);
}
else if (token == ')') {
while (opStack.top() != '(') {
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
// pop again to remove extra '(' from the stack
// as it is already paired with ')'
opStack.pop();
}
}
return postfix;
}
int main() {
// it stores infix expression
string infix;
cout << "Enter Infix Expression: ";
cin >> infix;
infix = "(" + infix + ")";
string postfix = convertInfixTopostfix(infix);
cout << "postfix Expression is: " << postfix << endl;
}
```

**Output**

```
Enter Infix Expression: a+b*(c/d*e)-f-g
Postfix Expression is: abcd/e**+f-g-
```

### Infix to Postfix second Approach ( for both left-associative and right-associative)

The problem with the previous algorithm is it cannot convert infix having right-associative operators like **“^”** **(exponential operator)** to postfix.

For example, if we use the first algorithm to convert **3^2^3** to postfix we get **3,2,^,3,^** which is wrong. The correct answer is **3,2,3,^,^**. This is because as **^** is **right-associative**. **3^2^3** is solved as **(3^(2^3)),** not as **((3^2)^3)**.

In this section, we will study how we can modify infix to postfix algorithm to include right-associative operators.

Before going further, we must remember that **left-associative and right-associative operators never have the same precedence** as it leads to ambiguity.

#### Steps

- Insert
**“(“**and**“)”**at the start and end of**infix expression**respectively. - Initialize a
**stack**, we call it**operator stack**. - Initialize a
**list**, name it**posfix**. - Scan
**infix expression**from left to right.- If the
**scanned character**is an**operand,**then push it to**postfix**. - If the
**scanned character**is**“(“**, then push it to the**stack**. - If the
**scanned character**is an**operator**,- If the top of the
**stack**is**“(“,**then push the**scanned character**to**stack**. - If the
**precedence**of the operator at top of the**stack**is less than**scanned character**, then push the**scanned character**to**stack**. - If the
**precedence**of the operator at top of the**stack**is more than**scanned character**, then**pop**the stack and push the popped character to**postfix**. - If the precedence of the operator at top of the
**stack**is equal to**scanned character**, then- If both the
**scanned character**and top of the**stack**are left-associative, then pop the stack and push the popped operator to**postfix**. - Otherwise, push the
**scanned character**to**postfix**.

- If both the
- Keep repeating the above 4 steps until we push the
**scanned character**to**postfix**.

- If the top of the

- If the
**scanned character**is**“)”**, keep popping operators from the**stack**and push them to**postfix**till we encounter**“(“**and then pop the remaining**“(“**.

- If the
- Keep repeating steps 4 until all input characters are read.
- The postfix expression will be saved in
**postfix**.

#### Pseudo Code

```
postfix: it stores the final postfix expression
opStack: it is the operator stack. It is used to store parenthesis and operators
infix: it stores the input infix expression
token: it stores infix character for each iteration
PUSH "(" AT BEGINNING OF infix
PUSH ")" AT END OF infix
FOR i = 1 to infix.LENGTH DO
token := infix[i]
IF token is "(" THEN
PUSH token TO opStack
ELSE IF token is operand THEN
PUSH token TO postfix
ELSE IF token is operator THEN
WHILE opStack.TOP is operator AND
(
(opStack.TOP Precedence > token Precedence) OR
((opStack.TOP Precedence == token Precedence) AND (Both opStack.TOP and token are Left-Associative))
) THEN
temp := opStack.TOP
opStack.POP
PUSH temp TO postfix
END WHILE
PUSH token TO opStack
ELSE if token is ")" THEN
WHILE opStack.TOP not equal to "(" THEN
temp := operatorStack.TOP
operatorStack.POP
PUSH temp TO postfix
END WHILE
opStack.POP
END ELIF
END FOR
```

Before moving to actual code, we will convert “**a+b*c^d^e-f/g*h**” into **postfix** using the above algorithm.

Operator | Precedence | Operator Associativity |
---|---|---|

+,- | 1 | Left to Right |

*,/ | 2 | Left to Right |

^ | 3 | Right to Left |

Infix Expression | Operator Stack | Postfix Expression | Description |
---|---|---|---|

(a+b*c^d^e-f/g*h) | ( | Push “(” to stack. | |

a+b*c^d^e-f/g*h) | ( | a | Push a to postfix. |

+b*c^d^e-f/g*h) | (+ | a | Push “+” to stack. |

b*c^d^e-f/g*h) | (+ | a,b | Push b to postfix. |

*c^d^e-f/g*h) | (+* | a,b | “*” has higher precedence than “+”, we do not pop stack. Push “*” to stack. |

c^d^e-f/g*h) | (+*( | a,b,c | Push c to postfix. |

^d^e-f/g*h) | (+*^ | a,b,c | “^” has higher precedence than “*”, we do not pop stack. Push “^” to stack. |

d^e-f/g*h) | (+*^ | a,b,c,d | Push d to postfix. |

^e-f/g*h) | (+*^^ | a,b,c,d | Scanned symbol (“^”) and stack top (“^”) have the same precedence but “^” is right-associative . Push “^” to stack. |

e-f/g*h) | (+*^^ | a,b,c,d,e | Push e to postfix. |

–f/g*h) | (- | a,b,c,d,e,^,^,*,+ | “^”,”*” have precedence greater than “-“. Pop “^” from stack to postfix. Pop “^” from stack to postfix. Pop “*” from stack to postfix. “+” and “-” have same precedence and both are left-associative. Pop “-” from stack to postfix. Push “-” to stack. |

f/g*h) | (- | a,b,c,d,e,^,^,*,+,f | Push f to postfix. |

/g*h) | (-/ | a,b,c,d,e,^,^,*,+,f | “/” have higher precedence than “-“. Push “/” to stack. |

g*h) | (-/ | a,b,c,d,e,^,^,*,+,f,g | Push g to postfix. |

*h) | (-* | a,b,c,d,e,^,^,*,+,f,g,/ | “*” and “/” have same precedence and both are left-associative. Pop “/” from stack to postfix. Push “*” to stack. |

h) | (-* | a,b,c,d,e,^,^,*,+,f,g./,h | Push h to postfix. |

) | a,b,c,d,e,^,^,*,+,f,g,/,h,*,- | Keep popping elements from stack to postfix till we encounter “(“. Pop “(” from the stack. |

#### Code

```
#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool isOperand(char t) {
if (t >= 'a' && t <= 'z') return true;
else return false;
}
bool isOperator(char t) {
switch (t) {
case '+':
case '-':
case '/':
case '*':
case '^':
return true;
}
return false;
}
// returns operator prece
int prece(char t) {
if (t == '+' || t == '-') return 1;
if (t == '*' || t == '/') return 2;
if (t == '^') return 3;
return 0;
}
// returns 1 for left associativity and 0 for right associativity
int assoc(char t) {
if (t == '+' || t == '-' || t == '*' || t == '*') return 1;
if (t == '^') return 0;
}
string convertInfixToPostfix(string infix) {
// operator stack
stack<char> opStack;
// it stores final postfix expression
string postfix;
// it stores each token of infix expression
char token;
postfix = "";
for (int i = 0; i < infix.length(); ++i) {
token = infix[i];
if (token == '(') {
opStack.push(token);
}
else if (isOperand(token)) {
postfix.push_back(token);
}
else if (isOperator(token)) {
while (isOperator(opStack.top()) && (
(prece(opStack.top()) > prece(token)) ||
(prece(opStack.top()) == prece(token) && assoc(opStack.top()) && assoc(token))
)
){
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
opStack.push(token);
}
else if (token == ')') {
while (opStack.top() != '(') {
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
// pop again to remove extra '(' from the stack
// as it is already paired with ')'
opStack.pop();
}
}
return postfix;
}
int main() {
// it stores infix expression
string infix;
cout << "Enter Infix Expression: ";
cin >> infix;
infix = "(" + infix + ")";
string postfix = convertInfixToPostfix(infix);
cout << "postfix Expression is: " << postfix << endl;
}
```

**Output**

```
Enter Infix Expression: a+b*c^d^e-f/g*h
postfix Expression is: abcde^^*+fg/h*-
```

**References**

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