Expression Evaluation (Cambridge (CIE) A Level Computer Science): Revision Note

Reverse Polish Notation (RPN)

What is RPN?

• Reverse Polish Notation (RPN) is a method of writing mathematical expressions where the operator comes after the operands

• This is also known as postfix notation

  • Infix: 3 + 4

  • RPN: 3 4 +

Why use RPN?

• No need for brackets: The order of operations is determined by position, not parentheses

• Easier for computers to evaluate using a stack

• Always unambiguous

How RPN works

• RPN uses a stack to evaluate expressions

1. Read from left to right

2. Push numbers onto the stack

3. When an operator is read:

   • Pop the top two values from the stack

   • Apply the operator

   • Push the result back onto the stack

4. When the expression ends, the final result is at the top of the stack

Example: evaluate 3 4 + 2 ×

• Final result: 14

Example: convert this infix expression to RPN

(7 − 2 + 8) / (9 − 5)

• Split the expression into parts:

• Left-hand side:

(7 − 2 + 8)

• This becomes:

( (7 − 2) + 8 )

• Which in RPN is:

7 2 − 8 +

• Right-hand side:

(9 − 5)

• In RPN:

9 5 −

• Combine with the division

• In RPN, that becomes:

7 2 − 8 + 9 5 − ÷

Summary