Evaluate Expression

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

The only argument given is character array A.

Return the value of arithmetic expression formed using reverse Polish Notation.

Input 1:
    A =   ["2", "1", "+", "3", "*"]
Output 1:
    9
Explaination 1:
    starting from backside:
    *: ( )*( )
    3: ()*(3)
    +: ( () + () )*(3)
    1: ( () + (1) )*(3)
    2: ( (2) + (1) )*(3)
    ((2)+(1))*(3) = 9
    
Input 2:
    A = ["4", "13", "5", "/", "+"]
Output 2:
    6
Explaination 2:
    +: ()+()
    /: ()+(() / ())
    5: ()+(() / (5))
    1: ()+((13) / (5))
    4: (4)+((13) / (5))
    (4)+((13) / (5)) = 6

Method:

Use a stack to keep track of the numbers, every time an operator is seen, pop two numbers and perform the operation.

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public int evalRPN(ArrayList<String> A) {
        Deque<String> stack = new ArrayDeque<>();
        int result = 0;
        for (String str : A) {
            if (isOperator(str)) {
                int b = Integer.valueOf(stack.pop());
                int a = Integer.valueOf(stack.pop());
                int temp = 0;
                if (str.equals("+")) {
                    temp = a + b;
                } else if (str.equals("-")) {
                    temp = a - b;
                } else if (str.equals("*")) {
                    temp = a * b;
                } else if (str.equals("/")) {
                    temp = a / b;
                }
                stack.push("" + temp);
            } else {
                stack.push(str);
            }
        }
        return Integer.valueOf(stack.pop());
    }
    
    private boolean isOperator(String str) {
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }
}