Some calculators take expressions in postfix order (also called reverse Polish notation): the operator comes after its two numbers. 3 4 + means 3 + 4, and 5 1 2 + 4 * + 3 - means 5 + (1 + 2) * 4 - 3.
Write a function that takes the expression as a list of tokens and returns its value. Tokens are whole numbers (possibly negative, like "-7") or one of +, -, *, /. Division keeps only the whole-number part, rounding toward zero: 7 / 2 is 3 and -7 / 2 is -3. The input is always a valid expression with no division by zero.
Write evaluate_postfix(tokens) in Python or evaluatePostfix(tokens) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
What does an operator need?
An operator needs the two most recent values that haven't been used yet. "Most recent" again points to a stack.
Step 2
Numbers go on the stack
Read tokens left to right. Push each number (converted to an integer).
Step 3
Operators take two off and put one back
For an operator, pop twice. The first pop is the right-hand number, the second is the left-hand number: for ["8", "2", "-"] that's 8 - 2, not 2 - 8. Compute the result and push it back.
Step 4
Watch the division rule
Python's // rounds down (-7 // 2 is -4), which isn't what's asked. Use int(a / b) in Python and Math.trunc(a / b) in JavaScript to round toward zero. At the end, the stack holds exactly one value: the answer.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Use a stack. Push numbers. For an operator, pop the right operand, then the left, apply the operator (truncating division toward zero) and push the result. Return the single value left on the stack.
python
1def evaluate_postfix(tokens):
2 stack = []
3 for token in tokens:
4 if token in ("+", "-", "*", "/"):
5 right = stack.pop()
↑popped FIRST: the right side
6 left = stack.pop()
↑then the left side
7 if token == "+":
8 stack.append(left + right)
9 elif token == "-":
10 stack.append(left - right)
11 elif token == "*":
12 stack.append(left * right)
13 else:
14 stack.append(int(left / right)) # rounds toward zero
↑round toward zero, not down
15 else:
16 stack.append(int(token))
↑numbers just wait on the stack
17 return stack[0]
javascript
1function evaluatePostfix(tokens) {
2 const stack = []
3 for (const token of tokens) {
4 if (["+", "-", "*", "/"].includes(token)) {
5 const right = stack.pop()
↑popped FIRST: the right side
6 const left = stack.pop()
↑then the left side
7 if (token === "+") stack.push(left + right)
8 else if (token === "-") stack.push(left - right)
9 else if (token === "*") stack.push(left * right)
10 else stack.push(Math.trunc(left / right)) // rounds toward zero
↑round toward zero, not down
11 } else {
12 stack.push(Number(token))
↑numbers just wait on the stack
13 }
14 }
15 return stack[0]
16}
Complexity
TimeO(n)SpaceO(n)
O(n) time for n tokens, and O(n) space for the stack in the worst case.
What we learned
Postfix expressions are designed for stacks: no brackets or precedence rules needed.
The order of operands matters for - and /: the first value popped is the right-hand side.
Language details matter in interviews: Python's // floors, while "round toward zero" needs int(a / b).