Reverse Polish Notation and Parsing

Reverse Polish Notation (RPN), also known as postfix notation, is a way of writing mathematical expressions without the need for parentheses or operator precedence rules. It is closely connected to how compilers evaluate expressions, and it relies on a stack for evaluation. Understanding RPN is essential for A-Level Theory of Computation.

---

Three Notations for Expressions

Notation	Name	Example (3 + 4 × 2)	Operator Position
Infix	Standard	3 + 4 × 2	Between operands
Prefix (Polish)	Prefix	+ 3 × 4 2	Before operands
Postfix (RPN)	Reverse Polish	3 4 2 × +	After operands

Infix is what humans use, but it requires:

• Parentheses to override precedence: (3 + 4) × 2 ≠ 3 + 4 × 2
• Precedence rules: × before +

RPN eliminates both problems. The order of operators and operands alone determines the evaluation.

---

Converting Infix to RPN

Method 1: Using a Parse Tree

1. Build a parse tree from the infix expression (using grammar rules for precedence).
2. Perform a post-order traversal (left, right, root).

Example: 3 + 4 × 2

Parse tree:

      +
     / \
    3   ×
       / \
      4   2

Post-order traversal: 3, 4, 2, ×, + → 3 4 2 × +

Method 2: The Shunting-Yard Algorithm (Dijkstra)

This algorithm converts infix to postfix using a stack for operators:

1. Read tokens from left to right.
2. If the token is a number, output it immediately.
3. If the token is an operator:
   • While the stack top has an operator with equal or greater precedence, pop it to the output.
   • Push the current operator onto the stack.
4. If the token is (, push it onto the stack.
5. If the token is ), pop operators to output until ( is found (discard the parentheses).
6. At the end, pop all remaining operators to the output.

Trace: Converting (3 + 4) × 2

Token	Action	Output	Stack
(	Push to stack		(
3	Output	3	(
+	Push to stack	3	( +
4	Output	3 4	( +
)	Pop until (	3 4 +
×	Push to stack	3 4 +	×
2	Output	3 4 + 2	×
End	Pop all	3 4 + 2 ×

Result: 3 4 + 2 × (which evaluates to 14).

---

Evaluating RPN Using a Stack

RPN expressions are evaluated left to right using a stack:

1. If the token is a number, push it onto the stack.
2. If the token is an operator, pop two operands, apply the operator, and push the result.

Trace: Evaluating 3 4 2 × +