Infix to Postfix

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

  1. Insert “(“ and “)” at the start and end of infix expression respectively.
  2. Initialize a stack, we call it operator stack.
  3. Initialize a list with name prefix.
  4. 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 “(“.
  5. Keep repeating steps 4 until all input characters are read.
  6. 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.

OperatorPrecedence
+,-1
*,/2
Precedence Table
Infix ExpressionOperator StackPostfix ExpressionDescription
(a+b*(c/d*e)-f-g)(Push “(” to stack.
a+b*(c/d*e)-f-g)(aPush a to postfix.
+b*(c/d*e)-f-g)(+aTop of the stack is “(“.
Push “+” to stack.
b*(c/d*e)-f-g)(+a,bPush b to postfix.
*(c/d*e)-f-g)(+*a,bSince “+” have lower precedence than “*”, we do not pop the stack.
Push “*” to stack.
(c/d*e)-f-g)(+*(a,bPush “(” to stack.
c/d*e)-f-g)(+*(a,b,cPush c to postfix.
/d*e)-f-g)(+*(/a,b,cTop of the stack is “(“.
Push “/” to stack.
d*e)-f-g)(+*(/a,b,c,dPush 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,/,ePush 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,*,*,+,fPush 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,-,gPush 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

  1. Insert “(“ and “)” at the start and end of infix expression respectively.
  2. Initialize a stack, we call it operator stack.
  3. Initialize a list, name it posfix.
  4. 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,
      1. If the top of the stack is “(“, then push the scanned character to stack.
      2. If the precedence of the operator at top of the stack is less than scanned character, then push the scanned character to stack.
      3. 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.
      4. 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.
      5. 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 “(“.
  5. Keep repeating steps 4 until all input characters are read.
  6. 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.

OperatorPrecedenceOperator Associativity
+,-1Left to Right
*,/2Left to Right
^3Right to Left
Precedence Table
Infix ExpressionOperator StackPostfix ExpressionDescription
(a+b*c^d^e-f/g*h)(Push “(” to stack.
a+b*c^d^e-f/g*h)(aPush a to postfix.
+b*c^d^e-f/g*h)(+aPush “+” to stack.
b*c^d^e-f/g*h)(+a,bPush 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,cPush 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,dPush d to postfix.
^e-f/g*h)(+*^^a,b,c,dScanned symbol (“^”) and stack top (“^”) have the same precedence but “^” is right-associative .
Push “^” to stack.
e-f/g*h)(+*^^a,b,c,d,ePush 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,^,^,*,+,fPush 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,gPush 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./,hPush 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.
Infx to Postfix Exmaple 2

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

Leave a Comment

Your email address will not be published. Required fields are marked *