Evaluate Reverse Polish Notation - 150

🔗LC150 🟡 Medium 🧩 Pattern – Stack

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.

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 = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Code language: JavaScript (javascript)

Solution

We use a stack to keep track of numbers, if we encounter an operand then we pop out the last two numbers that are in the stack and evaluate them.

📝 Note: For division, we use Math.truncate() to remove the decimal part.

/**
 * @param {string[]} tokens
 * @return {number}
 */
function evalRPN(tokens) {
    const stack = [];
    const operators = ['+', '-', '*', '/'];
    for (const token of tokens) {
        if (operators.includes(token)) {
            const num2 = stack.pop();
            const num1 = stack.pop();
            switch (token) {
                case '+':
                    stack.push(num1 + num2);
                    break;
                case '-':
                    stack.push(num1 - num2);
                    break;
                case '*':
                    stack.push(num1 * num2);
                    break;
                case '/':
                    stack.push(Math.trunc(num1 / num2));
                    break;
            }
        } else {
            stack.push(parseInt(token));
        }
    }
    return stack.pop();
}Code language: JavaScript (javascript)

Evaluate Reverse Polish Notation – 150

Example

Solution