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 +.
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 “(“.
- 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. |
c/d*e)-f-g) | (+*( | 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.
- Keep repeating the above 4 steps until we push the scanned character to postfix.
- If the scanned character is “)”, keep popping operators from the stack and push them to postfix till we encounter “(“ and then pop the remaining “(“.
- 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