Solution: Evaluate Reverse Polish Notation

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #150 (Medium): Evaluate Reverse Polish Notation

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

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

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Examples:

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

Example 2:
Input:	tokens = ["4","13","5","/","+"]
Output:	6
Explanation:	(4 + (13 / 5)) = 6

Example 3:
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

Constraints:

1 <= tokens.length <= 10^4
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Reverse Polish Notation was designed specifically to make computing easier with the more efficient use of a stack. So we can use a stack here to store numbers until they're used, and then each operand will use the top two values of the stack.

Since the order of the numbers is still important for subtraction and division, we'll have to make sure that the two numbers are processed in their original order, which is the opposite order of the stack.

After each successful operation, the result should be pushed back onto the stack until it's used. After iteration is complete, the remaining value in the stack will be our answer, so we should return stack[0].

Time Complexity: O(N) where N is the length of tokens

Space Complexity: O(N) for the length of the stack, up to N / 2 + 1 values

or O(1) with the use of an in-place stack

Implementation:

Javascript object values can be functions, so we can store the operations directly in an evaluate object as lambda functions.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

let a, b
const evaluate = {"+": ()=>a+b, "-": ()=>a-b, "*": ()=>a*b, "/": ()=>~~(a/b)}

var evalRPN = function(tokens) {
    let stack = []
    for (let t of tokens) {
        if (evaluate[t]) {
            b = stack.pop(), a = stack.pop()
            stack.push(evaluate[t]())
        } else stack.push(~~t)
    }
    return stack[0]
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if t not in {"+", "-", "*", "/"}:
                stack.append(int(t))
            else:
                b, a = stack.pop(), stack.pop()
                if t == "+": stack.append(a + b)
                elif t == "-": stack.append(a - b)
                elif t == "*": stack.append(a * b)
                else: stack.append(trunc(a / b))
        return stack[0]

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    private Set<String> ops = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String t : tokens) {
            if (!ops.contains(t)) stack.push(Integer.parseInt(t));
            else {
                int b = stack.pop(), a = stack.pop();
                if (t.equals("+")) stack.push(a + b);
                else if (t.equals("-")) stack.push(a - b);
                else if (t.equals("*")) stack.push(a * b);
                else stack.push(a / b);
            }
        }
        return stack.pop();
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

static unordered_set<string> ops({"+", "-", "*", "/"});

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stack;
        for (auto t : tokens) {
            if (ops.find(t) == ops.end()) stack.push(stoi(t));
            else {
                int b = stack.top(); stack.pop();
                int a = stack.top(); stack.pop();
                if (t == "+") stack.push(a + b);
                else if (t == "-") stack.push(a - b);
                else if (t == "*") stack.push(a * b);
                else stack.push(a / b);
            }
        }
        return stack.top();
    }
};