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 Complexity: O(N) Space Complexity: O(N)
Solution Code：
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<Integer>();
List<String> operators = Arrays.asList("+", "-", "*", "/");
for(String str: tokens) {
if(operators.contains(str)) {
int a = stack.pop();
int b = stack.pop();
if(str.equals("+")) {
stack.push(a + b);
}
else if(str.equals("-")) {
stack.push(b - a);
}
else if(str.equals("*")) {
stack.push(a * b);
}
else if(str.equals("/")) {
stack.push(b / a);
}
}
else {
stack.push(Integer.valueOf(str));
}
}
return stack.pop();
}
}
