Evaluate Reverse Polish Notation

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation (RPN).

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

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

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

Reverse Polish Notation (postfix notation) is naturally evaluated using a Stack. The core idea is that operands wait in the stack until an operator is encountered.

1. Initialize an empty stack to hold the numbers.
2. Iterate through each token in the tokens array:
   • If the token is an operator ('+', '-', '*', or '/'):
     • Pop the top two elements from the stack.
     • The first popped element is the right operand (b).
     • The second popped element is the left operand (a).
     • Apply the operator to a and b.
     • Important: For division, ensure you truncate toward zero. In JavaScript, you can use Math.trunc(a / b).
     • Push the result back onto the stack.
   • If the token is a number:
     • Convert it to an integer and push it onto the stack.
3. After processing all tokens, the stack will contain exactly one element, which is the final result of the expression. Return this element.

Solution

/**
 * @param {string[]} tokens
 * @return {number}
 */
function evalRPN(tokens) {
    const stack = [];
    const ops = {
        "+": (b, a) => a + b,
        "-": (b, a) => a - b,
        "*": (b, a) => a * b,
        "/": (b, a) => Math.trunc(a / b),
    };
    
    for (const token of tokens) {
        if (token in ops) {
            stack.push(ops[token](stack.pop(), stack.pop()));
        } else {
            stack.push(Number(token));
        }
    }
    
    return stack[0];
}

Complexity Analysis

• Time Complexity: $O(n)$, where $n$ is the length of the tokens array. We iterate through the array exactly once. Pushing to and popping from the stack takes $O(1)$ time.
• Space Complexity: $O(n)$ in the worst case (e.g., all tokens are numbers, or half the tokens are numbers before any operators). The stack will store at most $n/2 + 1$ elements.