Reverse Polish study guide

1. Identify the two forms

Infix notation places the operator between its operands, such as X - Y. RPN places the operator after the operands, such as X Y -. The central transformation is therefore not a change to the operands themselves; it is a change to the position of each operator so that the required operation is represented after the relevant sub-expression.

2. Preserve sub-expression structure

When converting an infix expression, first identify any grouped sub-expression. Convert that sub-expression to RPN, then place the operator that uses its result after the other required operand. For example:

(A + B) * C

The bracketed part becomes A B +. The complete expression then becomes A B + C *. The final * is placed after C because it operates on the result of A + B and on C.

For A * (B + C), the result is A B C + *. The order makes the addition occur before the multiplication, even though no brackets are present in the RPN expression.

3. Use the stack model to check a result

A useful exam check is to process the RPN expression from left to right. Operands are placed on a stack. An operator uses the relevant operands and its result is placed back on the stack. For 2 3 + 4 *, the first two operands are combined by +, giving the intermediate result 5. That result is then combined with 4 by *, giving 20. Therefore the RPN expression represents (2 + 3) * 4.

This check links the notation to its purpose: RPN gives an expression in a form suitable for evaluation using a stack. If an operator is encountered before the operands for its sub-expression have been represented, the transformation is probably incorrect.

4. Converting RPN back to infix

Read the RPN expression from left to right. When an operand is encountered, treat it as an expression. When an operator is encountered, combine the relevant preceding expressions with that operator and retain the grouping needed to show the structure clearly. For A B + C *, the first operator combines A and B, giving (A + B), and the final operator combines that result with C, giving (A + B) * C.

For A B C + *, the + first combines B and C; the * then combines A with that result, giving A * (B + C). Brackets may be needed in the infix form to preserve the grouping that RPN represented without brackets.

5. Exam application and self-check

When asked why RPN is used, connect all relevant points: it eliminates the need for brackets in sub-expressions, gives an order suitable for evaluation using a stack, and is used in interpreters based on a stack, including PostScript and bytecode. When asked to transform an expression, show the intermediate sub-expression reasoning rather than only writing the final sequence.

Before finalising an answer, check that every operator appears after the operands or completed sub-expressions on which it acts, that grouped infix structure has been preserved, and that a left-to-right stack trace would leave one final result for the complete expression.