Leetcode: Evaluate Reverse Polish Notation

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

Analysis:
First of all, we must figure out what is the "Reverse Polish Notation"? According to the wiki, RPN is a mathematical notation in which every operator follows all its operands. It is also known as postfix notation. E.g.
3 4 +  is postfix notation
+ 3 4 is prefix notation
3 + 4 is infix notation

If there are multiple operations, the operator is given immediately after the second operand. 
For e.g. 2 1 + 3 *   - > (2 + 1) * 3 = 9
3 4 5 * -   ->  3 - (4 * 5)  = -17
3 4 - 5 *   ->  (3 - 4) * 5 = -5

Solution:
From the analysis, it's not hard to see that we can use stack to store the digital numbers. 
For instance, for the expression of RPN 3 4 - 5 *, we first push 3 and 4 into the stack, when we see an operator - , we pop 3 and 4 and performs 3 - 4. Note that the first pop-out number will be the second operand. Then we push back the result into the stack. Now the stack has -1 and 5. When we see the operator * we repeat the same operations until we reach the last token.

Code (Java):

public class Solution {
    public int evalRPN(String[] tokens) {
        // if empty or null
        if (tokens == null || tokens.length == 0) return 0;
        
        Stack<Integer> stack = new Stack<Integer>();
        int result = 0;
        
        for (int i = 0; i < tokens.length; i++) {
            if (!isOperator(tokens[i])) {
                stack.push(Integer.valueOf(tokens[i]));
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                result = calculation(operand1, operand2, tokens[i]);
                
                // push back the intermediate results
                stack.push(result);
            }
        }
        return stack.pop();
    }
    
    private boolean isOperator(String str) {
        return (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"));
    }
    
    private int calculation(int op1, int op2, String operator) {
        int result = 0;
        if (operator.equals("+")) {
             result = op1 + op2;
        } else if (operator.equals("-")) {
            result = op1 - op2;
        } else if (operator.equals("*")) {
            result = op1 * op2;
        } else if (operator.equals("/")) {
            result = op1 / op2;
        }
        return result;
    }
}

Discussion:
The solution is very straight forward. For the time complexity, it is O(n) because we only need to traverse the input array of string only once. Let's look at how much space is consumed. For input with n tokens, it needs push at most n / 2 tokens into the stack, as roughly the rest half is operators. So the space complexity for this solution is O(n). 

Summary:
The crux of the problem is to get idea behind the RPN. In the code interview, the interviewer may not explain to you very details. Maybe they will only show you the definition and several examples. So before you jump into any solution, make the best clear of the problem. In this problem, it is critical to understand "If there are multiple operations, the operator is given immediately after the second operand". That is the key to come out the stack solution.