Evaluate Reverse Polish Notation
- 1 min read
- Stacks
- LC-Medium
3 years ago
Solution
- Just use a stack
- When in an interview, be sure to double check the order of operators
- Remember this: Since it's a stack, the orders are reversed, so always put
ybeforex. This of course doesn't matter for addition and multiplication, but do it just to be safe.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def evalRPN(self, tokens: List[str]) -> int:
stack = []
ops = {
'+': lambda x, y: x + y,
'-': lambda x, y: y - x,
'/': lambda x, y: int(y / x),
'*': lambda x, y: x * y
}
for token in tokens:
if token in ops:
op1, op2 = stack.pop(), stack.pop()
stack.append(ops[token](op1, op2))
else:
stack.append(int(token))
return stack.pop()