Description
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Solution
Stack, time O(n), space O(n)
原来String也可以switch case的啊。。比if else简洁多啦。
class Solution {
public int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<>();
for (String s : tokens) {
switch (s) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
stack.push(-stack.pop() + stack.pop());
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
int a = stack.pop();
stack.push(stack.pop() / a);
break;
default:
stack.push(Integer.parseInt(s));
break;
}
}
return stack.pop();
}
}
