AlgoVerse

Evaluating postfix

Evaluate a postfix expression with a stack in one pass: a number is pushed, and each operator pops the top two numbers and pushes the result.

In a postfix expression each operator comes right after its operands, so one stack evaluates it in one pass:

Read the full explanation ↓
Input:
expr="62/3-42*+"PDF export

62/3-42*+ means (6/2 − 3) + 4·2 = 8.

  1. def evaluate_postfix(expr):
  2. # Operands are single digits; / is whole-number division.
  3. stack = []
  4. for i in range(len(expr)):
  5. ch = expr[i]
  6. if ch.isdigit():
  7. stack.append(int(ch))
  8. continue
  9. if len(stack) < 2:
  10. return None
  11. b = stack.pop()
  12. a = stack.pop()
  13. if ch == "+":
  14. value = a + b
  15. elif ch == "-":
  16. value = a - b
  17. elif ch == "*":
  18. value = a * b
  19. else:
  20. if b == 0:
  21. return None
  22. value = a // b
  23. stack.append(value)
  24. if len(stack) != 1:
  25. return None
  26. return stack[0]

Invariant: The stack always holds the values of the subexpressions finished so far whose operator has not come yet.

Start

012345678
62/3-42*+
stack—

Local variables

expr'62/3-42*+'

Orange = changed in this step

Call stack

  1. evaluate_postfix()line 1
Step 1 of 72
Black = apply · Orange = key steppush: 0/5 · apply: 0/4 · result: 0/1
    Explanation

    The idea

    In a postfix expression each operator comes right after its operands, so one stack evaluates it in one pass:

    • push a number;
    • apply an operator to the top two numbers (the first one popped is the second operand) and push the result.

    At the end exactly one number must be left: the answer.

    Why a stack?

    Each finished subexpression is one number on the stack; an operator always needs the two subexpressions finished last, which are the top two numbers. Compilers and HP calculators work this way.

    What to watch in the trace

    • Follow the stack card; each operator takes two numbers off and puts one back.