How do you solve Evaluate Reverse Polish Notation?

Iterate through tokens. For operands, convert to integer and push onto the stack. For operators, pop the top two operands, apply the operator in correct order (paying attention to subtraction and division), and push the result back. After processing all tokens, the stack contains the final result. This approach runs in O(n) time with O(n) space.

What pattern does Evaluate Reverse Polish Notation use?

The Pattern: Stack (Expression Evaluation) The Heuristic: Use a stack to store operands and apply operators to the top two elements, ensuring correct operand order and enabling linear-time evaluation of postfix expressions.

Evaluate Reverse Polish Notation

Q: What is the time complexity of Evaluate Reverse Polish Notation?

O(n). Each token is processed exactly once. Stack push and pop operations are O(1), so total time is linear in the number of tokens.

Problem

Given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation, return the evaluation of the expression.

1 ≤ tokens.length ≤ 10⁴
tokens[i] is either an operator: '+', '-', '*', or '/', or an integer in string format
The given RPN expression is always valid

Example

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

Output: 9

The expression corresponds to ((2 + 1) * 3). The algorithm processes tokens sequentially: push 2 and 1 onto the stack, encounter '+', pop 1 and 2, compute 2 + 1 = 3, push 3 back. Next, push 3, encounter '*', pop 3 and 3, compute 3 * 3 = 9, push 9. The final stack top is 9, the result.

Approach

Straightforward Solution

A naive approach might try to recursively parse the expression or convert it to infix notation, which is complex and inefficient. Alternatively, scanning tokens and evaluating operators immediately without a stack would fail to maintain correct operand order.

Core Observation

Reverse Polish Notation expressions can be evaluated using a stack because each operator applies to the two most recent operands. This last-in-first-out property aligns naturally with stack operations.

Path to Optimal

Preview

The key recognition signals are 'Reverse Polish Notation', 'operators apply to previous two operands', and 'evaluate expression'. These indicate the Stack pattern because the problem requires last-in-first-out access to operands…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through tokens. For operands, convert to integer and push onto the stack…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each token is processed exactly once. Stack push and pop operations are O(1), so total time is linear in the number of tokens.

Space

O(n)

In the worst case, all tokens are operands and pushed onto the stack, requiring O(n) auxiliary space proportional to input size.

Solution

Python

1class Solution:
  def evalRPN(self, tokens: list[str]) -> int:
      stack = []
      for c in tokens:
          if c == "+":
              stack.append(stack.pop() + stack.pop())
          elif c == "-":
              a, b = stack.pop(), stack.pop()
              stack.append(b - a)
          elif c == "*":
              stack.append(stack.pop() * stack.pop())
          elif c == "/":
              a, b = stack.pop(), stack.pop()
              stack.append(int(b / a))
          else:
              stack.append(int(c))
      return stack[0]

Step-by-Step Solution

1

Initialize an Empty Stack to Store Operands

3	`stack = []`

Objective

To prepare a data structure that will hold operands and intermediate results during evaluation.

Key Insight

A stack perfectly models the evaluation order of Reverse Polish Notation expressions. By pushing operands and popping them when an operator is encountered, the algorithm maintains the correct order of operations without recursion or complex parsing.

Interview Quick-Check

Core Logic

The stack stores operands and intermediate results, enabling last-in-first-out access required by RPN evaluation.

Common Pitfalls & Bugs

Using a queue or list without stack semantics would fail to maintain correct operand order.

2

Iterate Through Tokens and Evaluate Expression Using Stack Operations

To process each token, pushing operands or applying operators to the top two operands on the stack.

3

Return the Final Result from the Stack

To output the evaluated integer result after processing all tokens.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 6 Critical

stack.append(stack.pop() + stack.pop())

Pop the top two operands, add them, and push the result back onto the stack.

This line performs the core arithmetic operation for addition, combining the two most recent operands and maintaining the stack state for further evaluation.

Line 11 Critical

stack.append(stack.pop() * stack.pop())

Pop the top two operands, multiply them, and push the result.

This line executes the multiplication operation and maintains the stack state for further processing.

Line 14 Critical

stack.append(int(b / a))

Perform integer division with truncation toward zero and push the result.

Using int(b / a) ensures division truncates toward zero as required, which differs from floor division and is critical for correctness.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why must the operator apply to the two most recently pushed operands, and why is operand order important for subtraction and division?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Evaluate Reverse Polish Notation from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Evaluate Reverse Polish Notation drill

or drill a free problem

1	`class Solution:`
2	`def evalRPN(self, tokens: list[str]) -> int:`
3	`stack = []`
4	`for c in tokens:`
5	`if c == "+":`
6	`stack.append(stack.pop() + stack.pop())`
7	`elif c == "-":`
8	`a, b = stack.pop(), stack.pop()`
9	`stack.append(b - a)`
10	`elif c == "*":`
11	`stack.append(stack.pop() * stack.pop())`
12	`elif c == "/":`
13	`a, b = stack.pop(), stack.pop()`
14	`stack.append(int(b / a))`
15	`else:`
16	`stack.append(int(c))`
17	`return stack[0]`