Evaluate Reverse Polish Notation

Problem Description

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation (postfix 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.

Examples

Constraints

• 1 <= tokens.length <= 10⁴
• tokens[i] is either an operator or an integer in the range [-200, 200].

Stack for Postfix Operators

In Reverse Polish Notation, operators follow their operands. This order matches a Last-In, First-Out (LIFO) stack. We iterate through the tokens. If the token is a number, we push it onto the stack. If it is an operator, we pop the top two numbers from the stack, perform the operation, and push the result back onto the stack. By the end of the tokens array, the stack will contain exactly one number, which is the final evaluated result.

Solution 1: Operand Stack Evaluation

Use a stack to store intermediate operands and evaluate values.

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            } else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        for token in tokens:
            if token == "+":
                stack.append(stack.pop() + stack.pop())
            elif token == "-":
                b = stack.pop()
                a = stack.pop()
                stack.append(a - b)
            elif token == "*":
                stack.append(stack.pop() * stack.pop())
            elif token == "/":
                b = stack.pop()
                a = stack.pop()
                # Python integer division truncates toward zero differently for negative numbers
                stack.append(int(a / b))
            else:
                stack.append(int(token))
        return stack[0]

#include <vector>
#include <string>
#include <stack>

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::stack<int> stack;
        for (const std::string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int b = stack.top(); stack.pop();
                int a = stack.top(); stack.pop();
                if (token == "+") stack.push(a + b);
                else if (token == "-") stack.push(a - b);
                else if (token == "*") stack.push(a * b);
                else if (token == "/") stack.push(a / b);
            } else {
                stack.push(std::stoi(token));
            }
        }
        return stack.top();
    }
};

Complexity Analysis

• Time Complexity: O(n) where n is the number of tokens, as we process each token exactly once.
• Space Complexity: O(n) auxiliary space to store elements in the operand stack.

Where It Breaks

If the expression contains numbers or operations that exceed 32-bit signed integer limits (which can cause overflows), this implementation fails. Although intermediate values are guaranteed to fit in a 32-bit integer by problem constraints, safety checks are needed in production math parsing.

Common Mistakes

• Incorrect division truncation in Python: Using a // b instead of int(a / b). In Python, // rounds down toward negative infinity (e.g., -6 // 132 is -1), whereas the problem requires truncating toward zero (which int(-0.045) correctly handles as 0).
• Operand order swap: When subtracting or dividing, the first element popped is the right operand b (denominator), and the second element popped is the left operand a (numerator). Reversing this order yields incorrect math values.

Frequently Asked Questions

Why is postfix notation useful? Postfix expressions do not require parentheses to specify the order of operations, resolving operator precedence ambiguity.

How does division behave in Python? In Python, dividing integers using / returns a float. Wrapping the division in int(...) discards the decimal portion, satisfying the requirement to truncate toward zero.

← All Problems