Coding Interview PatternsEvaluate Reverse Polish Notation
MediumStacks

Evaluate Reverse Polish Notation

Explanation & Solution

Practice Problem

Description

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation.

Evaluate the expression and 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 reverse polish notation.
Input:tokens = ["2","1","+","3","*"]
0
2
1
1
2
+
3
3
4
*

Output: 9

Explanation: ((2 + 1) * 3) = 9

Constraints

  • 1 <= tokens.length <= 10^4
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200]

Approach

Stacks pattern

1. Initialize a Stack

  • Use a stack to hold operands as we process each token

2. Process Each Token

  • If the token is a number, push it onto the stack
  • If the token is an operator (+, -, *, /):
  • Pop the top two elements: b (top), then a (second)
  • Compute a operator b
  • Push the result back onto the stack

3. Handle Division

  • Use Math.trunc() to truncate toward zero (not Math.floor)
  • This matches the problem's requirement for integer division

4. Return Result

  • After processing all tokens, the stack contains exactly one element — the final result

Key Insight

  • RPN eliminates the need for parentheses and operator precedence rules
  • The stack naturally handles the order of operations — operands are consumed as soon as their operator appears
  • Time: O(n), Space: O(n)

Solution Code

Previous
Min Stack
Next
Daily Temperatures