Infix to Reverse Polish Notation Arithmetic Conversion

Infix to Reverse Polish Notation Conversion Rules – To convert an expression from infix notation to reverse polish notation, we need to scan the notation from left to right. and for each operand and operator that comes, we need to follow some rules –

1. If the operand is a variable or a constant, then we need to push it into the stack
2. For the operator, pop the top two data from the stack and perform the operator. and then push the result into the stack.

Let’s understand the conversion using examples.

Example 1 – Convert the following numerical arithmetic expression into RPN and show the stack operations for evaluating the numerical result ( 3 * 4) + (5 * 6).

Solution – In reverse Polish notation, the given numerical arithmetic expression is written as 34 * 56 * +

The stack operation for the given expression is shown in the figure below. Each box represents one stack operation, and the arrow always points to the top of the stack.

First, the number 3 is pushed onto the stack, and then the number 4. The next symbol is the multiplication operator *. This causes a multiplication of the two topmost data in the stack. The stack is popped, and the product is placed on the top of the stack.

Now the numbers 5 and 6 are pushed into the stack. The next symbol is the multiplication operator *, which causes a multiplication of the two top-most data in the stack. again the stack is popped, and the product of two numbers is placed on the top of the stack. The last operation causes an arithmetic addition of the two topmost numbers in the stack. The final result is 42, which is stored into stack again.

Example – Convert the following arithmetic expressions from infix to Reverse Polish notation (RPN).

1. A * B + C * D + E * F
2. A * B + A * (B * D + C * E)
3. A + B * [C * D + E * (F + G)]
4. A * [B + C * (D + E)]/[F * (G+H)]

Solution

(i) A * B + C * D + E * F
= (AB*) + (CD*) + (EF*)
= (AB * CD* +) + (EF*)
= (AB * CD* +) + (EF*)
= AB*CD* + EF* +

(ii) A * B + A * (B*D + C*E)
= A*B +A*(BD*CE*+)
= (AB*) +(BD*CE*+A*)

(iii) A+B*[C*D+E*(F+G)]
= A +B *[C*D+E*(FG+)]
= A +B*[C*D+FG+E*]
= A+B*[(CD*) + (FG+E*]
= A +B * [CD*FG + E*+]
= A + CD*FG + E* + B*
= CD * FG + E* + B*A +

(iv) A*[B+C*(D+E)]/[F*(G+H)]
= A*[B+C*(DE+)]/[F*(GH+)]
= A*[B+DE+C*]/GH+F*
= A*[DE+C*B+]/F*GH+
= DE+C*B+A*/F*GH+
= DE + C*B + A*F*GH +/

Related questions and answers