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 Sam K., 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

More Stacks practice problems

See all Stacks problems →