Evaluate Reverse Polish Notation

Problem Statement

LeetCode-150: You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

• The valid operators are ‘+’, ‘-’, ‘*’, and ‘/’.
• The input represents a valid arithmetic expression in a reverse polish notation.
• There will not be any division by zero.

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9


Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Approach

Based on the Reverse Polish Notation, we can observe that the operands are placed before the operators. In other words, anytime we see an operand, we need to evaluate the last two values.

Now these two values can be the result of some previous evaluation or the operands themselves. So, we can use a stack to store the operands and evaluate the expression.

On a high level, the algorithm can be described as follows:

1. Iterate over the tokens.
2. If the token is an operand, push it to the stack.
3. If the token is an operator, pop the last two operands from the stack, evaluate the expression and push the result back to the stack.
4. At the end of the iteration, the stack will have only one element which is the result of the expression.
5. Return the result.

Implementation

Here is a Java implementation of the above approach:

private static final Map<String, BiFunction<Integer, Integer, Integer>> op = new HashMap<>();
static{
    op.put("+", (a,b) -> a+b);
    op.put("-", (a,b) -> a-b);
    op.put("*", (a,b) -> a*b);
    op.put("/", (a,b) -> a/b);
}

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    
    for(String token : tokens){
        if(op.containsKey(token)){
            int one = stack.pop();
            int two = stack.pop();
            stack.push(op.get(token).apply(two, one));
        }else{
            stack.push(Integer.parseInt(token));
        }
    }   
    return stack.pop();
}

Complexity Analysis

The time complexity for this approach is $O(N)$ where $N$ is the number of tokens in the input array. This is because we iterate over the tokens once and perform a constant time operation for each token.

Due to the associated Stack, the space complexity is also $O(N)$ where $N$ is the number of tokens in the input array.