Evaluating a Postfix Expression

5 3 - 2 x
token  action                       stack
5      push 5                       [5]
3      push 3                       [5, 3]
-      5 - 3 = 2                    [2]
2      push 2                       [2, 2]
x      2 x 2 = 4                    [4]
answer: 4

2 3 +          = 2 + 3            -> 5
5 3 -          = 5 - 3            -> 2
2 3 4 x +      = 2 + 3 x 4        -> 14
2 3 + 4 x      = (2 + 3) x 4      -> 20
2 3 2 ^ ^      = 2 ^ (3 ^ 2)      -> 512
2 3 ^ 2 ^      = (2 ^ 3) ^ 2      -> 64
10 2 / 3 -     = 10 / 2 - 3       -> 2.0

2 +      refused (not enough operands): operator '+' needs two operands
2 3      refused (two values left): the expression left 2 values, not 1
4 0 /    refused (division by zero): division by zero in the expression

Two rows settle chapter 36's warning with arithmetic: 2 3 2 ^ ^ is 512 and 2 3 ^ 2 ^ is 64. Those are the postfix forms of 2 ^ (3 ^ 2) and (2 ^ 3) ^ 2, and the difference is entirely in the order of the symbols.

Rows three and four are the same check for precedence: 2 3 4 x + is 14 and 2 3 + 4 x is 20.

Conversion and evaluation together

The two chapters compose: convert an infix expression, then evaluate the result, and compare against the value the expression should have.

PRECEDENCE = {"+": 1, "-": 1, "x": 2, "/": 2, "^": 3}
RIGHT = {"^"}


def to_postfix(tokens):
    output, stack = [], []
    for token in tokens:
        if token not in PRECEDENCE and token not in "()":
            output.append(token)
        elif token == "(":
            stack.append(token)
        elif token == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()
        else:
            while (stack and stack[-1] != "("
                   and (PRECEDENCE[stack[-1]] > PRECEDENCE[token]
                        or (PRECEDENCE[stack[-1]] == PRECEDENCE[token]
                            and token not in RIGHT))):
                output.append(stack.pop())
            stack.append(token)
    while stack:
        output.append(stack.pop())
    return output


def evaluate(tokens):
    stack = []
    for token in tokens:
        if token in PRECEDENCE:
            right, left = stack.pop(), stack.pop()
            stack.append({"+": left + right, "-": left - right,
                          "x": left * right, "/": left / right,
                          "^": left ** right}[token])
        else:
            stack.append(int(token))
    return stack[0]


checks = [
    ("2 + 3 x 4",            2 + 3 * 4),
    ("( 2 + 3 ) x 4",        (2 + 3) * 4),
    ("10 / 2 - 3",           10 / 2 - 3),
    ("2 ^ 3 ^ 2",            2 ** 3 ** 2),
    ("7 - 2 - 1",            7 - 2 - 1),
    ("2 x ( 3 + 4 ) / 7",    2 * (3 + 4) / 7),
]
print("%-22s %-20s %-8s %-8s %s" % ("infix", "postfix", "ours", "Python", "agree"))
for infix, expected in checks:
    postfix = to_postfix(infix.split())
    ours = evaluate(postfix)
    print("%-22s %-20s %-8s %-8s %s"
          % (infix, " ".join(postfix), ours, expected, ours == expected))

infix                  postfix              ours     Python   agree
2 + 3 x 4              2 3 4 x +            14       14       True
( 2 + 3 ) x 4          2 3 + 4 x            20       20       True
10 / 2 - 3             10 2 / 3 -           2.0      2.0      True
2 ^ 3 ^ 2              2 3 2 ^ ^            512      512      True
7 - 2 - 1              7 2 - 1 -            4        4        True
2 x ( 3 + 4 ) / 7      2 3 4 + x 7 /        2.0      2.0      True

Every row is checked against Python's own evaluation of the same expression, which knows nothing about our stack. Six independent agreements, including both associativity cases.

The cost

One pass, one push or one pop pair per token: O(n) time. The stack holds at most the operands not yet consumed, so O(n) memory, worst case for an expression like 1 2 3 4 5 + + + +.

Quick revision

• Push operands; on an operator pop two, apply, push the result; one value should remain at the end.
• The first value popped is the RIGHT operand. This matters for -, /, % and ^ and hides for +

and x.

• No precedence and no brackets are needed: the conversion already resolved them.
• 2 3 2 ^ ^ is 512 and 2 3 ^ 2 ^ is 64.
• Errors: too few operands for an operator; more than one value left at the end; division by zero.
• O(n) time and O(n) memory.

Test yourself

1. Give the evaluation algorithm in two lines. Push each operand. On each operator, pop two values, apply the operator and push the result. At the end exactly one value remains and it is the answer.

2. Which popped value is the right operand, and which operators does it matter for? The first one popped. It matters for -, /, % and ^; for + and x the mistake is invisible.

3. Evaluate 5 3 - 2 x step by step. Push 5, push 3; the - pops 3 then 5 and pushes 5 - 3 = 2; push 2; the x pops 2 and 2 and pushes 4. The answer is 4.

4. Evaluate 2 3 2 ^ ^ and 2 3 ^ 2 ^, and say which infix expressions they are. 512 and 64. They are 2 ^ (3 ^ 2) and (2 ^ 3) ^ 2.

5. Name three errors the evaluator must detect. An operator with fewer than two operands available; more than one value remaining at the end; and division by zero.

6. Why does evaluation need no precedence rules? Because the postfix form already encodes the grouping in the order of its symbols, which is exactly what the conversion did.