150. Evaluate Reverse Polish Notation

In this problem, we are going to write a program which calculates the value of Reverse Polish notation.

Here are some quick thoughts on how to solve this:

• If the token is an operator, we gonna use the value of the two previous numbers for the calculation.
• And since we want to get the latest elements that we have, Stack will be helpful.

Using Stack
For example, we have a notation: ["4","13","5","/","+"].
Since the first 3 elements are integer, the stack will push all 3 of them in: stack = ["4", "13", "5"].
Then, the next token is: "/", which is an operator. We pop the two latest element in the stack, which is "13", and "5" to conduct the division, stack = ["4"]. The result is 2 since we just take the int value. We push that 2 back in the stack. stack = ["4", "2"].
Lastly, "+" is an operator token, we pop "4" and "2" from the stack to conduct the addition, stack = []. The result is "6". Push "6" back into the stack, stack = ["6"].
Since there is no more token to visit, the final result is returned, which is 6.

With this example, we have the algorithm:

1. Initialize an empty Stack.
2. Traverse through each token in the tokens list.
3. If a token is not an operator, add it to the stack.
4. If the token is an operator: pop the two latest element in the stack, compute based on the operator and push back the result
5. Return the last element in stack after visiting all the tokens.

Here is the solution in Java

class Solution {
    public boolean contains(String[] operators, String token) {
        for (String op: operators) {
            if (op.equals(token)) {
                return true;
            }
        }
        return false;
    } 
    public int evalRPN(String[] tokens) {
        /**
        Reverse polish notation:
        3 4 + => 3 + 4
        3 4 x 5 6 x + => 3 * 4 + 5 * 6

        - When we hit an operator, pop out the latest 2 operands and calculate the result
            Then put back the result into the stack for later calculation
        - Return the last elements in the stack which is the final result
        */

        String[] operators = {"+", "-", "*", "/"};
        Stack<String> stack = new Stack<>();

        for (String t: tokens) {
            // System.out.println(stack.toString());
            if (!contains(operators, t)) {
                stack.push(t);
            } else {
                int second = Integer.parseInt(stack.pop());
                int first = Integer.parseInt(stack.pop());
                int result;
                if (t.equals("+")) {
                    result = first + second;
                } else if (t.equals("-")) {
                    result = first - second;
                } else if (t.equals("*")) {
                    result = first * second;
                } else {
                    result = first / second;
                }

                stack.push(String.valueOf(result));
            }
        }

        return Integer.parseInt(stack.pop());
    }
}