Evaluate a postfix expression
A tiny expression engine accepts a calculation already written in postfix — operands first, operator after — and works it out.
- Tokens are either decimal integers or one of + - * /.
- Division is integer division, and every division in the cases is exact.
- There are never too few operands; the tokens always evaluate cleanly.
- An empty token list evaluates to zero.
evaluate_postfix(tokens: list<string>) → int
Where you start
def evaluate_postfix(tokens: list[str]) -> int:
Worked examples
| Call | Result |
|---|---|
evaluate_postfix(["3", "4", "+"]) | 7 |
evaluate_postfix(["10", "3", "-"]) | 7 |
evaluate_postfix(["2", "3", "*", "4", "+"]) | 10 |
evaluate_postfix(["12", "4", "/"]) | 3 |
Hint
One stack. Push numbers; when an operator arrives, pop two, apply it, push the result back.
Reference solution in Python
def evaluate_postfix(tokens: list[str]) -> int:
stack = []
for tok in tokens:
if len(tok) > 1 or tok.isdigit():
stack.append(int(tok))
else:
b = stack.pop()
a = stack.pop()
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
return stack[-1] if stack else 0