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