Postfix Expressions

Convert Infix to Postfix notation

An infix and postfix are the expressions. An expression consists of constants, variables, and symbols. Symbols can be operators or parenthesis. All these components must be arranged according to a set of rules so that all these expressions can be evaluated using the set of rules.

Examples of expressions are:

5 + 6

A - B

(P * 5)

All the above expressions have a common structure, i.e., we have an operator between the two operands. An Operand is an object or a value on which the operation is to be performed. In the above expressions, 5, 6 are the operands while '+', '-', and '*' are the operators.

What is infix notation?

When the operator is written in between the operands, then it is known as infix notation. Operand does not have to be always a constant or a variable; it can also be an expression itself.

For example,

(p + q) * (r + s)

In the above expression, both the expressions of the multiplication operator are the operands, i.e., (p + q), and (r + s) are the operands.

In the above expression, there are three operators. The operands for the first plus operator are p and q, the operands for the second plus operator are r and s. While performing the operations on the expression, we need to follow some set of rules to evaluate the result. In the above expression, addition operation would be performed on the two expressions, i.e., p+q and r+s, and then the multiplication operation would be performed.

Syntax of infix notation is given below:

<operand> <operator> <operand>

If there is only one operator in the expression, we do not require applying any rule. For example, 5 + 2; in this expression, addition operation can be performed between the two operands (5 and 2), and the result of the operation would be 7.

If there are multiple operators in the expression, then some rule needs to be followed to evaluate the expression.

If the expression is:

4 + 6 * 2

If the plus operator is evaluated first, then the expression would look like:

10 * 2 = 20

If the multiplication operator is evaluated first, then the expression would look like:

4 + 12 = 16

The above problem can be resolved by following the operator precedence rules. In the algebraic expression, the order of the operator precedence is given in the below table:

Operators	Symbols
Parenthesis	( ), {}, [ ]
Exponents	^
Multiplication and Division	*, /
Addition and Subtraction	+ , -

The first preference is given to the parenthesis; then next preference is given to the exponents. In the case of multiple exponent operators, then the operation will be applied from right to left.

For example:

2^2^3 = 2 ^ 8

= 256

After exponent, multiplication, and division operators are evaluated. If both the operators are present in the expression, then the operation will be applied from left to right.

The next preference is given to addition and subtraction. If both the operators are available in the expression, then we go from left to right.

The operators that have the same precedence termed as operator associativity. If we go from left to right, then it is known as left-associative. If we go from right to left, then it is known as right-associative.

Problem with infix notation

To evaluate the infix expression, we should know about the operator precedence rules, and if the operators have the same precedence, then we should follow the associativity rules. The use of parenthesis is very important in infix notation to control the order in which the operation to be performed. Parenthesis improves the readability of the expression. An infix expression is the most common way of writing expression, but it is not easy to parse and evaluate the infix expression without ambiguity. So, mathematicians and logicians studied this problem and discovered two other ways of writing expressions which are prefix and postfix. Both expressions do not require any parenthesis and can be parsed without ambiguity. It does not require operator precedence and associativity rules.

Postfix Expression

The postfix expression is an expression in which the operator is written after the operands. For example, the postfix expression of infix notation ( 2+3) can be written as 23+.

Some key points regarding the postfix expression are:

• In postfix expression, operations are performed in the order in which they have written from left to right.
• It does not any require any parenthesis.
• We do not need to apply operator precedence rules and associativity rules.

Algorithm to evaluate the postfix expression

• Scan the expression from left to right until we encounter any operator.
• Perform the operation
• Replace the expression with its computed value.
• Repeat the steps from 1 to 3 until no more operators exist.

Let's understand the above algorithm through an example.

Infix expression: 2 + 3 * 4

We will start scanning from the left most of the expression. The multiplication operator is an operator that appears first while scanning from left to right. Now, the expression would be:

Expression = 2 + 34*

= 2 + 12

Again, we will scan from left to right, and the expression would be:

Expression = 2 12 +

= 14

Evaluation of postfix expression using stack.

• Scan the expression from left to right.
• If we encounter any operand in the expression, then we push the operand in the stack.
• When we encounter any operator in the expression, then we pop the corresponding operands from the stack.
• When we finish with the scanning of the expression, the final value remains in the stack.

Let's understand the evaluation of postfix expression using stack.

Example 1: Postfix expression: 2 3 4 * +

Input	Stack
2 3 4 * +	empty	Push 2
3 4 * +	2	Push 3
4 * +	3 2	Push 4
* +	4 3 2	Pop 4 and 3, and perform 4*3 = 12. Push 12 into the stack.
+	12 2	Pop 12 and 2 from the stack, and perform 12+2 = 14. Push 14 into the stack.

The result of the above expression is 14.

Example 2: Postfix expression: 3 4 * 2 5 * +

Input	Stack
3 4 * 2 5 * +	empty	Push 3
4 * 2 5 * +	3	Push 4
*2 5 * +	4 3	Pop 3 and 4 from the stack and perform 3*4 = 12. Push 12 into the stack.
2 5 * +	12	Push 2
5 * +	2 12	Push 5
*+	5 2 12	Pop 5 and 2 from the stack and perform 5*2 = 10. Push 10 into the stack.
+	10 12	Pop 10 and 12 from the stack and perform 10+12 = 22. Push 22 into the stack.

The result of the above expression is 22.

Algorithm to evaluate postfix expression

1. Read a character
2. If the character is a digit, convert the character into int and push the integer into the stack.
3. If the character is an operator,
   • Pop the elements from the stack twice obtaining two operands.
   • Perform the operation
   • Push the result into the stack.

Conversion of infix to postfix

Here, we will use the stack data structure for the conversion of infix expression to prefix expression. Whenever an operator will encounter, we push operator into the stack. If we encounter an operand, then we append the operand to the expression.

Rules for the conversion from infix to postfix expression

1. Print the operand as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator on to the stack.
3. If the incoming symbol is '(', push it on to the stack.
4. If the incoming symbol is ')', pop the stack and print the operators until the left parenthesis is found.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has lower precedence than the top of the stack, pop and print the top of the stack. Then test the incoming operator against the new top of the stack.
7. If the incoming operator has the same precedence with the top of the stack then use the associativity rules. If the associativity is from left to right then pop and print the top of the stack then push the incoming operator. If the associativity is from right to left then push the incoming operator.
8. At the end of the expression, pop and print all the operators of the stack.

Let's understand through an example.

Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Input Expression	Stack	Postfix Expression
K		K
+	+
L	+	K L
-	-	K L+
M	-	K L+ M
*	- *	K L+ M
N	- *	K L + M N
+	+	KL+MN*K L + M N* -
(	+ (	K L + M N *-
O	+ (	K L + M N * - O
^	+ ( ^	K L + M N* - O
P	+ ( ^	K L + M N* - O P
)	+	K L + M N* - O P ^
*	+ *	K L + M N* - O P ^
W	+ *	K L + M N* - O P ^ W
/	+ /	K L + M N* - O P ^ W *
U	+ /	K L + M N* - O P ^W*U
/	+ /	K L + M N* - O P ^W*U/
V	+ /	KL + MN*-OP^W*U/V
*	+ *	KL+MN*-OP^W*U/V/
T	+ *	KL+MN*-OP^W*U/V/T
+	+	KL+MN*-OP^W*U/V/T* KL+MN*-OP^W*U/V/T*+
Q	+	KL+MN*-OP^W*U/V/T*Q
		KL+MN*-OP^W*U/V/T*+Q+

The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V * T + Q) is KL+MN*-OP^W*U/V/T*+Q+.