Show understanding of how Reverse Polish Notation (RPN) can be used to carry out the evaluation of expressions

16.2 Translation Software – Reverse Polish Notation (RPN)

Learning Objective

Show understanding of how Reverse Polish Notation (RPN) can be used to carry out the evaluation of expressions.

What is Reverse Polish Notation?

RPN, also known as postfix notation, writes the operator after its operands.

An expression such as \$a + b \times c\$ in infix form becomes \$a\;b\;c\;\times\;+\$ in RPN.

Why Use RPN?

• No need for parentheses – the order of evaluation is implicit.
• Evaluation can be performed using a simple stack algorithm.
• Many calculators and some compilers use RPN for efficiency.

Converting Infix to Postfix (RPN)

The Shunting‑Yard algorithm (invented by Dijkstra) is commonly used. The key rules are:

1. Read the infix expression from left to right.
2. When an operand is encountered, output it immediately.
3. When an operator is encountered, pop operators from the stack to the output while they have higher or equal precedence (and are left‑associative). Then push the new operator.
4. When a left parenthesis ‘(’ is encountered, push it onto the stack.
5. When a right parenthesis ‘)’ is encountered, pop and output operators until the matching ‘(’ is removed.
6. After the whole expression has been read, pop any remaining operators to the output.

Example: Convert and Evaluate

Infix expression: \$\bigl( 3 + 4 \bigr) \times 5 - 6 \div 2\$

Step 1 – Convert to RPN

Applying the Shunting‑Yard algorithm gives the postfix form:

RPN: \$3\;4\;+\;5\;\times\;6\;2\;\div\;-\$

Step 2 – Evaluate the RPN Expression

The evaluation uses a stack. For each token:

• If it is an operand, push it onto the stack.
• If it is an operator, pop the required number of operands, apply the operator, and push the result back.

Stack Trace

Final result of the expression is 32.

Algorithm in Pseudocode

Below is a language‑independent description of the RPN evaluation algorithm.

function evaluateRPN(tokens):
stack ← empty list
for each token in tokens:
if token is a number:
push token onto stack
else if token is an operator:
operand2 ← pop stack
operand1 ← pop stack
result ← apply operator to operand1 and operand2
push result onto stack
return pop stack   // final result

Key Points for Examination

• Understand the difference between infix, prefix and postfix notations.
• Be able to convert an infix expression to RPN using the Shunting‑Yard rules.
• Know the stack‑based evaluation steps and be able to trace the stack contents.
• Remember operator precedence and associativity when converting.
• Be comfortable writing the evaluation algorithm in pseudocode or a simple programming language.