How do you approach Evaluate Reverse Polish Notation?

In postfix notation, an operator applies to the two most recently produced values.

What is the time complexity of Evaluate Reverse Polish Notation?

Time complexity: O(n). Space complexity: O(n) for the stack.

What are common mistakes on Evaluate Reverse Polish Notation?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

Sitelet https://gitgood.dev/coding/evaluate-reverse-polish-notation

gitGood.dev

← Back to problems

Evaluate Reverse Polish Notation

MediumData Structures

Description

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (postfix notation). Evaluate the expression and return an integer.

Rules:

The valid operators are +, -, *, and /.
Each operand may be an integer or another expression.
Division between two integers always truncates toward zero.
There will be no division by zero.
The answer and all intermediate calculations fit in a 32-bit integer.

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

Constraints

- 1 <= tokens.length <= 10^4 - tokens[i] is either an operator ("+", "-", "*", "/") or an integer in the range [-200, 200]. - The input always represents a valid RPN expression.

Evaluate Reverse Polish Notation: approach, complexity and pitfalls

A medium stack problem, graded against 7 test cases (4 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

In postfix notation, an operator applies to the two most recently produced values.
Push numbers onto a stack; on an operator, pop two operands, apply it, and push the result. Pop order matters for - and /.
Two classic bugs: treating "-11" as an operator instead of a number, and using floor division (Python // rounds toward negative infinity) instead of truncation toward zero.

The optimal approach

Show the approach: Operand Stack

Scan the tokens left to right. Push numbers; on an operator, pop the right operand `b`, then the left operand `a`, compute `a op b`, and push the result. The final stack holds one value - the answer.

Two details trip people up: a token like `"-11"` is a *number* (check for exact operator match, not just a leading `-`), and division must truncate toward zero - in Python `int(a / b)` does this while `a // b` floors; in JavaScript use `Math.trunc`.

Time: O(n)
Space: O(n) for the stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.