150. Evaluate Reverse Polish Notation Medium

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 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

Approach

Input: An array of strings tokens, representing a Reverse Polish Notation expression Output: Return the integer result of the evaluated expression

This problem is a typical Stack + Expression Evaluation problem.

In Reverse Polish Notation (postfix expression), an operator always applies to the two nearest operands preceding it. Therefore, we can use a stack to simulate the entire computation process:

• When a number is encountered: Convert it to an integer and push it onto the stack.
• When an operator is encountered: Pop two numbers from the stack, perform the calculation according to the operator, and push the result back onto the stack.
• After traversal is complete: The only element remaining in the stack is the final result of the expression.

Implementation

python

from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            # Check if it is an operand (integer, including negative numbers)
            if token.lstrip('-').isdigit():
                stack.append(int(token))  # Convert to integer and push to stack
            else:
                # Encountered an operator, pop the top two numbers (the first popped is the right operand)
                b = stack.pop()
                a = stack.pop()
                
                # Perform calculation based on the operator
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                elif token == '/':
                    # The problem requires integer division that truncates toward zero 
                    # (not floor division like // in Python), so use int(a / b)
                    stack.append(int(a / b))
        
        # The last remaining element in the stack is the calculated result
        return stack[0]

javascript

/**
 * @param {string[]} tokens
 * @return {number}
 */
const evalRPN = function(tokens) {
    const stack = [];

    for (t of tokens) {
        if (/-?[0-9]+/.test(t)) {
            stack.push(parseInt(t));
        } else {
            const r = stack.pop();
            const l = stack.pop();

            if (t == '+') {
                stack.push(l + r);
            } else if (t == '-') {
                stack.push(l - r);
            } else if (t == '*') {
                stack.push(l * r);
            } else {
                stack.push(parseInt(l / r));
            }
        }
    }

    return stack.reduce((acc, curr) => acc + curr, 0);
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

150. Evaluate Reverse Polish Notation (English)

150. 逆波兰表达式求值 (Chinese)