A stack of operands

Evaluating anything with structure: push values, and let each operator consume what it needs.

Key idea

The evaluation loop

A stack machine reads a sequence of instructions left to right. A value is pushed. An operation pops the arguments it needs, computes, and pushes the result back. When the input runs out, the answer is the single thing left.

This is how a great many real evaluators work, and once the loop is in your fingers it handles anything with the same structure.

1def run_machine(program):2    """push <n>, dup, add, mul, neg."""3    stack = []4    for step in program:5        if step == "dup":6            stack.append(stack[-1])7        elif step == "add":8            b, a = stack.pop(), stack.pop()9            stack.append(a + b)10        elif step == "mul":11            b, a = stack.pop(), stack.pop()12            stack.append(a * b)13        elif step == "neg":14            stack.append(-stack.pop())15        else:16            stack.append(int(step))17    return stack[-1]18 19print(run_machine(["3", "dup", "mul"]))20print(run_machine(["5", "2", "add", "neg"]))

Gotcha

The operands come off backward

This is the bug that catches everyone once. The stack returns the most recent value first, so the second operand comes off first.

b, a = stack.pop(), stack.pop() names them in the order they were pushed, so a - b and a / b mean what they look like. Getting this backward is invisible for add and mul, which are commutative, and wrong for sub and div. Test subtraction specifically or you will not notice.

1stack = [10, 3]              # 10 was pushed first, then 32 3b, a = stack.pop(), stack.pop()4print(a, b, a - b)           # 10 - 3, which is what the input meant

Edge cases

Integer division truncates the wrong way

Python's // rounds toward negative infinity, so -7 // 2 is -4. Most expression evaluators specify truncation toward zero, which would give -3.

When a problem says division truncates toward zero, int(a / b) gives that behavior for the range these problems use. This is the Unit 0 floor-division fact showing up somewhere it actually changes an answer, and it is a genuinely common wrong submission.

1print(-7 // 2)              # floor division, toward negative infinity2print(int(-7 / 2))          # truncation, toward zero

Predict the output· 5 min

Predict the output: operand order

Both functions evaluate the same subtraction, and they disagree. Type the two values separated by a space.

Python

1def careless(tokens):2    stack = []3    for token in tokens:4        if token == "-":5            a, b = stack.pop(), stack.pop()6            stack.append(a - b)7        else:8            stack.append(int(token))9    return stack[-1]10 11def careful(tokens):12    stack = []13    for token in tokens:14        if token == "-":15            b, a = stack.pop(), stack.pop()16            stack.append(a - b)17        else:18            stack.append(int(token))19    return stack[-1]20 21print(careless(["10", "3", "-"]), careful(["10", "3", "-"]))

Printed output

Problem· 20 min

Evaluate Reverse Polish Notation

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def run_machine(program):2 """push <n>, dup, add, mul, neg."""3 stack = []4 for step in program:5 if step == "dup":6 stack.append(stack[-1])7 elif step == "add":8 b, a = stack.pop(), stack.pop()9 stack.append(a + b)10 elif step == "mul":11 b, a = stack.pop(), stack.pop()12 stack.append(a * b)13 elif step == "neg":14 stack.append(-stack.pop())15 else:16 stack.append(int(step))17 return stack[-1]18 19print(run_machine(["3", "dup", "mul"]))20print(run_machine(["5", "2", "add", "neg"]))

1def careless(tokens):2 stack = []3 for token in tokens:4 if token == "-":5 a, b = stack.pop(), stack.pop()6 stack.append(a - b)7 else:8 stack.append(int(token))9 return stack[-1]10 11def careful(tokens):12 stack = []13 for token in tokens:14 if token == "-":15 b, a = stack.pop(), stack.pop()16 stack.append(a - b)17 else:18 stack.append(int(token))19 return stack[-1]20 21print(careless(["10", "3", "-"]), careful(["10", "3", "-"]))