Skip to main content

150. Evaluate Reverse Polish Notation

medium

Evaluate a postfix arithmetic expression given as tokens. The cleanest 'use a stack' problem — a building block for calculator and parser interview rounds.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Postfix is designed for a stack — that's the whole point of the notation.

Hint 2

Scan tokens left to right: push numbers, on operator pop two operands, compute, push the result.

Hint 3

Order of operands matters for non-commutative ops: pop b first, then a. Compute a OP b — not b OP a.

Hint 4

For division, truncate toward zero (not floor). Watch out for negative results.

Solution approach

Reveal approach

Single pass with an integer stack. For each token: if it's a number, push it; if it's an operator, pop the top two values — call the first one popped b and the second a — compute a OP b, and push the result. Final result is the single value left on the stack. Watch out for two language gotchas: division must truncate toward zero (Python's // floor-divides for negatives, so use int(a / b) or a Decimal-style trunc), and operand order matters for - and / — popping reverses the order in which the operands appeared in tokens, so it's a OP b, not b OP a. O(n) time, O(n) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • math
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • LinkedIn
  • Meta

Practice these live with InterviewChamp.AI

Drill Evaluate Reverse Polish Notation and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →