Evaluate Reverse Polish Notation — Operand Stack
Advertisement
Problem 269 · Evaluate Reverse Polish Notation
Difficulty: Medium · Pattern: Operand Stack
Solutions
# Python
def evalRPN(tokens):
stack = []
ops = {'+': lambda a,b: a+b, '-': lambda a,b: a-b,
'*': lambda a,b: a*b, '/': lambda a,b: int(a/b)}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop()
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]
// Java
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String t : tokens) {
if ("+-*/".contains(t)) {
int b = stack.pop(), a = stack.pop();
switch(t) {
case "+": stack.push(a+b); break;
case "-": stack.push(a-b); break;
case "*": stack.push(a*b); break;
case "/": stack.push(a/b); break;
}
} else stack.push(Integer.parseInt(t));
}
return stack.pop();
}
Complexity
- Time: O(n)
- Space: O(n)
Advertisement