#150

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Evaluate Reverse Polish Notation

Compute the result of an arithmetic expression in Reverse Polish Notation using a stack to manage operands efficiently.

Problem Statement

You are given an array of strings, tokens, representing an arithmetic expression in Reverse Polish Notation. Each token is either an integer or one of the operators '+', '-', '*', or '/'. Evaluate the expression and return the integer result.

Ensure your solution correctly processes all tokens using a stack to manage intermediate values. Handle integer division by truncating toward zero and consider edge cases where operators may appear consecutively or numbers are negative.

Examples

Example 1

Input: tokens = ["2","1","+","3","*"]

Output: 9

((2 + 1) * 3) = 9

Example 2

Input: tokens = ["4","13","5","/","+"]

Output: 6

(4 + (13 / 5)) = 6

Example 3

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

Output: 22

((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 <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Solution Approach

Stack-Based Evaluation

Initialize an empty stack. Iterate through each token: if it is a number, push it onto the stack; if it is an operator, pop the last two numbers, apply the operator, and push the result back. Continue until all tokens are processed, then return the final value from the stack.

Integer Division Handling

For the division operator '/', ensure the result truncates toward zero rather than flooring. Convert the operands to integers before division, and handle negative values carefully to match problem requirements and avoid unexpected results.

Edge Case Considerations

Check for expressions with a single number, consecutive operators, or negative numbers. Avoid stack underflow by confirming two operands are available before applying an operator, and validate input length constraints to prevent runtime errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each token is processed exactly once. Space complexity is O(n) in the worst case due to the stack holding all operands before operators reduce them.

What Interviewers Usually Probe

Asks about stack implementation details and handling integer division.
Questions around edge cases with negative numbers or consecutive operators.
Wants reasoning for why a stack is preferred over direct array manipulation.

Common Pitfalls or Variants

Common pitfalls

Using float division instead of truncating toward zero, causing wrong integer results.
Popping operands in the wrong order, reversing the operation result.
Not handling edge cases like a single token or negative numbers correctly.

Follow-up variants

Evaluate expressions with additional operators like modulus or exponentiation.
Handle Reverse Polish Notation with variables replaced by lookup values.
Compute expressions using a recursive approach instead of an explicit stack.

FAQ

What is the best approach for Evaluate Reverse Polish Notation?

Use a stack to push numbers and apply operators in order, popping two operands for each operator and pushing the result.

How should integer division be handled in this problem?

Division must truncate toward zero. Convert operands to integers before dividing and handle negative numbers carefully.

Can the input contain negative numbers or single-token expressions?

Yes, the solution must correctly handle negative numbers and expressions consisting of a single numeric token.

What is the time and space complexity?

Time complexity is O(n) because each token is processed once. Space complexity is O(n) due to the stack storing operands.

Why is a stack necessary for this pattern?

A stack efficiently manages the state of operands, allowing operators to access the most recent numbers in Reverse Polish Notation order.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

import operator


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        opt = {
            "+": operator.add,
            "-": operator.sub,
            "*": operator.mul,
            "/": operator.truediv,
        }
        s = []
        for token in tokens:
            if token in opt:
                s.append(int(opt[token](s.pop(-2), s.pop(-1))))
            else:
                s.append(int(token))
        return s[0]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

import operator


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        opt = {
            "+": operator.add,
            "-": operator.sub,
            "*": operator.mul,
            "/": operator.truediv,
        }
        s = []
        for token in tokens:
            if token in opt:
                s.append(int(opt[token](s.pop(-2), s.pop(-1))))
            else:
                s.append(int(token))
        return s[0]

Continue Practicing

#149 max points on a line #189 rotate array #204 count primes