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
思路：
- 用栈记录数组前面未进行运算的值。
- 遍历数组。遇到数字直接入栈；遇到运算符号，出栈两个数字进行运算，将结果入栈。
- 最后返回栈中元素就是表达式计算结果。
- 注意除法和减法，出栈数字的运算顺序。
public int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<>();
for (String val : tokens) {
if (val.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if (val.equals("-")) {
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
} else if (val.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if (val.equals("/")) {
int a = stack.pop();
int b = stack.pop();
stack.push(b / a);
} else if (Integer.valueOf(val) >= 0) {
stack.push(Integer.valueOf(val));
} else {
return -1;
}
}
return stack.pop();
}