Description
Evaluate a valid postfix expression containing signed integers and +, -, *, or /. Division truncates toward zero. Intermediate values fit a signed 32-bit integer.
Solution
def eval_rpn(tokens):
stack = []
for token in tokens:
if token not in {"+", "-", "*", "/"}:
stack.append(int(token))
continue
right, left = stack.pop(), stack.pop()
if token == "+":
value = left + right
elif token == "-":
value = left - right
elif token == "*":
value = left * right
else:
value = abs(left) // abs(right)
if (left < 0) != (right < 0):
value = -value
stack.append(value)
return stack[-1]Examples
Example 1
- Input
[["2","1","+","3","*"]]- Output
9
(2 + 1) times 3 is 9.
Example 2
- Input
[["4","13","5","/","+"]]- Output
6
13 / 5 truncates to 2.
Example 3
- Input
[["-7","3","/"]]- Output
-2
Division truncates toward zero, not downward.
Approach
Push each number. An operator consumes the last two numbers: the first popped value is the right operand and the second is the left. Compute their result and push it back.
Time & space
O(n) time and O(n) auxiliary space, where n is the token count.