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();
    }
}