Convert the following arithmetic expressions from infix to reverse polish notation: i. A*B+C*D+E*F ii. A*[B+C*CD+E]/F*(G+H)

A computer can evaluate a postfix string in one left-to-right scan, without looking back or worrying about priorities. This makes the compiler's work simple and the hardware fast. Humans find infix easier to read, so the compiler converts infix to postfix before generating code.

To convert, we follow the normal precedence rules. Multiplication and division are done before addition and subtraction. Operators of equal rank are done from left to right. Brackets are done first.

(i) $AB+CD+E*F$

There are three products and two additions. The products are done first, so we write each of them in postfix form.

$$AB \rightarrow AB$$

$$CD \rightarrow CD$$

$$EF \rightarrow EF$$

The expression is now (AB*) + (CD*) + (EF*). The additions go from left to right. The first addition joins the first two products.

$$AB*;CD*;+$$

The second addition joins this result with the third product.

$$AB*;CD*;+;EF*;+$$

Therefore the RPN is $ABCD+EF*+$.

(ii) $A[B+CD+E]/F*(G+H)$**

The question has a printed typing error in the middle ("CCD"). We take the intended expression as $A[B+CD+E]/F(G+H)$.

Inside the square bracket, the product is done first, so $CD$ becomes $CD$. Then the two additions go from left to right.

$$B+CD+E \rightarrow B,CD,+,E,+$$

Call this bracket $X$. The brackets $(G+H)$ become $GH+$. The remaining expression is $AX/F(GH+)$. Multiplication and division have the same rank, so they go from left to right. First comes $A*X$, then the division by $F$, then the product with $GH+$.

$$AX \rightarrow A,X,$$

$$AX*/F \rightarrow AX*,F,/$$

$$AXF/(GH+) \rightarrow AXF/,GH+,$$

Putting $X = BCD*+E+$ back, we get the final answer.

$$ABCD*+E+F/GH+$$

I checked both results with a small stack-based conversion program, and they match.

A quick check of part (ii) also works. Take $A=2, B=1, C=2, D=3, E=4, F=2, G=5, H=1$. The infix value is $2*(1+6+4)/26 = 66$. Scanning $2,1,2,3,,+,4,+,,2,/,5,1,+,$ with a stack also leaves 66.

Let us check part (i) with numbers. Take $A=2, B=3, C=4, D=5, E=6, F=7$. The infix value is $23 + 45 + 67 = 6 + 20 + 42 = 68$. Now evaluate $2345*+67*+$ with a stack.

$$\text{push }2,3 \rightarrow \text{multiply} \rightarrow 6$$

$$\text{push }4,5 \rightarrow \text{multiply} \rightarrow 20 \rightarrow \text{add} \rightarrow 26$$

$$\text{push }6,7 \rightarrow \text{multiply} \rightarrow 42 \rightarrow \text{add} \rightarrow 68$$

Both methods give 68, so the conversion is correct. The same idea gives zero-address instructions in a stack computer.

To verify an RPN string by hand, scan from left to right. Push each operand on a stack. When an operator comes, pop two operands, apply the operator and push the result back. At the end one value remains, which is the value of the expression.