Reverse Polish revision notes

What Reverse Polish notation is

An expression in infix form places an operator between its operands, for example A + B. In Reverse Polish notation (RPN), also called postfix form, the operator is placed after its operands: A B +.

Why RPN is used

RPN eliminates the need for brackets in sub-expressions. The order of the operands and operators gives the order in which operations are carried out. This makes an expression suitable for evaluation using a stack. RPN is used in interpreters based on a stack, for example PostScript and bytecode.

Converting infix to RPN

For a simple expression, write operands in their original order and place each operator after the operands that it acts on. Brackets used to show grouping do not appear in the resulting RPN expression.

Example:

A + B becomes A B +.

For a grouped expression, convert the inner expression first and then place the outer operator after the completed operands:

(A + B) * C becomes A B + C *.

The + is written after A and B, because it acts on that sub-expression. The * is written after the result of A + B and C.

Another example is:

A * (B + C) becomes A B C + *.

Here, B C + represents the bracketed sub-expression. The multiplication operator follows it because multiplication uses A and the result of the addition.

Evaluating RPN with a stack

Read the RPN expression from left to right. An operand is placed on the stack. When an operator is reached, it is applied to the relevant operands on the stack, and the resulting value is placed back on the stack. At the end, the result of the expression is available from the stack.

For 2 3 +, place 2 and then 3 on the stack. The + uses these two operands and produces 5.

For 2 3 + 4 *, the addition is completed first, producing 5; the multiplication then uses 5 and 4, producing 20. This corresponds to (2 + 3) * 4 without requiring brackets in the RPN form.

Common errors

• Writing the operator between operands instead of after them.
• Removing brackets without preserving the grouping they represented.
• Placing an outer operator before the RPN representation of its sub-expression is complete.
• Treating RPN as if it were ordinary infix notation.
• Forgetting that an RPN expression is intended to provide an order suitable for stack evaluation.