Evaluate a Postfix Expression
MediumStack
Problem
A pocket calculator stores formulas in postfix order: operands come first and each operator follows its two operands. For example, 3 4 + means 3 + 4, and 2 3 4 * + means 2 + 3 · 4.
You are given the formula as an array of tokens tokens. Each token is an integer or one of +, -, *, /. Division between integers truncates toward zero (so -7 / 2 = -3). Return the value of the formula.
Example 1
- Input:
- tokens = ["4", "13", "5", "/", "+"]
- Output:
- 6
13 / 5 = 2, then 4 + 2 = 6.
Example 2
- Input:
- tokens = ["3", "-4", "*", "2", "-"]
- Output:
- -14
3 · (-4) = -12, then -12 - 2 = -14.
Constraints
- 1 ≤ tokens.length ≤ 10^4
- The formula is valid and never divides by zero
- Every operand and intermediate value fits in a 32-bit signed integer
Hint
Show the first hint
When you read an operator, where are its two operands?
Walkthrough
How to approach it
01Clarify before coding
- How does division round? Toward zero, not toward negative infinity.
- Are negative numbers tokens like "-4"? Yes; a lone "-" is the operator.
- Is the input always valid? Yes, so the stack ends with exactly one value.
02Brute force
Repeatedly find the first operator, combine it with the two tokens before it, splice the result into the list, and repeat.
Cost: Each splice is O(n) and there are up to n/2 operators: O(n²).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.