Reverse Polish notation

Infix and postfix, converting both ways, evaluating RPN with a stack, and the shunting-yard algorithm.

A6.6Theory of computationA level25 min

You write sums as 3 + 4 × 2, with the operator between its two operands. That is infix notation, and it needs rules to be understood: multiplication before addition, left to right otherwise, and brackets to override both. A computer evaluating an expression would rather not deal with any of that. Reverse Polish notation (RPN), also called postfix, puts each operator after its operands, and then needs no brackets and no precedence rules at all.

Infix and postfix

Compare the second and third rows. In infix only the brackets tell them apart; in RPN the order of the symbols does. The numbers stay in the same order as in the infix; only the operators move.

The name comes from Polish notation (prefix, operator first: + 3 4), devised by the Polish logician Jan Łukasiewicz. "Reverse" puts the operator last.

Why and where RPN is used

• No brackets or precedence. An RPN expression is read strictly left to right, so there is nothing to look ahead for.
• It suits a stack. Operands are pushed; an operator pops its operands and pushes the answer. The evaluator is a few lines long and needs no parsing of priorities.
• Stack-based interpreters use it. Compilers and interpreters turn infix source code into postfix-ordered instructions for a stack machine: Java bytecode and Python bytecode both work this way, and so does the PostScript language used by printers. Some calculators, notably older Hewlett-Packard models, take input in RPN.

Converting infix to RPN by hand

1. Put in brackets to show the order the operations happen, one pair per operator: 3 + 4 × 2 becomes (3 + (4 × 2)).
2. Working from the innermost brackets out, move each operator to just after its two operands and drop the brackets: (4 × 2) becomes 4 2 ×, then (3 + 4 2 ×) becomes 3 4 2 × +.

Another way is to draw the expression as a tree, with each operator above its two operands, and write it out in post-order: left subtree, right subtree, then the node. That is where the name postfix comes from.

To go from RPN back to infix, read left to right with a stack of expressions. Push each operand. For each operator, pop two expressions, join them with the operator between them in brackets, and push the result. For 5 1 − 2 6 + ×: push 5, push 1, − gives (5 − 1), push 2, push 6, + gives (2 + 6), and × gives ((5 − 1) × (2 + 6)). Drop any brackets that precedence makes unnecessary.

Evaluating RPN with a stack

Read the tokens left to right:

• a number: push it;
• an operator: pop the top item into right, pop the next into left, work out left operator right, and push the answer.

At the end, exactly one item should be left: the value. The order of the two pops matters for − and /: the item popped first is the right operand.

Tracing 5 1 − 2 6 + × 4 /, with the top of the stack on the right:

In AQA-style pseudo-code, with Push and Pop on a stack:

FOR EACH token IN tokens
  IF token is a number THEN
    Push(token)
  ELSE
    right ← Pop()
    left ← Pop()
    Push(apply token to left and right)
  ENDIF
ENDFOR
OUTPUT Pop()

And in Python, using a list as the stack, printing the stack after every token:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def evaluate(rpn):
    stack = []
    for token in rpn.split():
        if token in "+-*/":
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:
                stack.append(left / right)
        else:
            stack.append(int(token))
        print(f"{token:>2}  {stack}")
    return stack.pop()

print("value:", evaluate("5 1 - 2 6 + * 4 /"))

Run this in the simulator

Python writes * for × and - for −. The last line shows 8.0, because / always gives a float in Python. If an operator finds fewer than two items on the stack, or more than one item is left at the end, the expression was not valid RPN.

Converting infix to RPN with a program

Edsger Dijkstra's shunting-yard algorithm converts infix to RPN with a stack for operators. Give * and / a higher precedence than + and -. Then, reading the infix tokens left to right:

1. A number goes straight to the output.
2. An operator: while the top of the stack is an operator of higher or equal precedence, pop it to the output. Then push the new operator.
3. An opening bracket is pushed.
4. A closing bracket: pop operators to the output until the opening bracket is on top, then pop the bracket and throw it away.
5. When the tokens run out, pop everything left on the stack to the output.

Tracing 3 + 4 * 2: 3 is output; + is pushed; 4 is output; * has higher precedence than the + on top, so nothing is popped and * is pushed; 2 is output; at the end * then + are popped. The output is 3 4 2 * +. The "or equal" in step 2 is what makes 8 - 2 - 3 come out as 8 2 - 3 -, working left to right.

Task: an RPN calculator

Write both halves of a calculator for expressions with whole numbers, +, -, *, / and brackets. In every expression, tokens are separated by single spaces, including the brackets.

• to_rpn(infix) takes an infix string such as "( 3 + 4 ) * 2" and returns the RPN string with single spaces, such as "3 4 + 2 *". Use the shunting-yard algorithm with a stack. All four operators work left to right.
• evaluate(rpn) takes an RPN string and returns its value, using a list as a stack. / is ordinary division; every test divides exactly.
• Do not use Python's eval.
• For each expression in tests, in order, print the infix, ->, the RPN, =, then the value as a whole number. For example 3 + 4 * 2 -> 3 4 2 * + = 11. Four lines in all.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tests = ["3 + 4 * 2", "( 3 + 4 ) * 2", "( 5 - 1 ) * ( 2 + 6 ) / 4", "8 - 2 - 3"]

def to_rpn(infix):
    output = []
    stack = []
    return ""

Challenges

1. Convert (a + b) × (c − d) / e to RPN by hand, then check it with your to_rpn.
2. Make evaluate print invalid instead of crashing for 4 + and for 1 2 3 +.
3. Add ^ for powers. Powers work right to left: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2). What must change in step 2 of the algorithm?