Evaluate an expression written in postfix order

Scan the tokens with a stack of numbers. A number is pushed. An operator pops the right operand, then the left, applies the operation and pushes the result. At the end the stack holds exactly one number: the answer. O(n) time and space.

Order matters for - and /: the first pop is the right operand.

Truncating toward zero in Python needs int(a / b) or sign handling; // rounds down, which differs for negative results.

Postfix needs no brackets or precedence rules, which is why stack machines and some calculators use it.

def eval_postfix(tokens: list[str]) -> int:
    nums: list[int] = []
    for tok in tokens:
        if tok in ("+", "-", "*", "/"):
            right, left = nums.pop(), nums.pop()
            if tok == "+":
                nums.append(left + right)
            elif tok == "-":
                nums.append(left - right)
            elif tok == "*":
                nums.append(left * right)
            else:
                q = abs(left) // abs(right)
                nums.append(q if (left < 0) == (right < 0) else -q)
        else:
            nums.append(int(tok))
    return nums[0]

Common mistakes

• Using // for division and getting -4 instead of -3 for -7 / 2.
• Popping operands in the wrong order.

Call out the truncation rule and how you handle it in Python.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you evaluate normal infix expressions?

   Show hint

   Shunting-yard to convert to postfix, or two stacks for numbers and operators.

2. How do you avoid float rounding in the division?

   Show hint

   Divide absolute values with // and fix the sign.