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 +.

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.

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.

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