Evaluate Reverse Polish Notation
Medium · Stack & Strings · Array · Math · Stack
Problem
You are given a list of strings tokens that describes an arithmetic expression in Reverse Polish Notation (postfix form): every operator comes right after its two operands. Evaluate the expression and return its value.
- The operators are +, -, * and /. Each operand is an integer or the result of an earlier part of the expression.
- Division between integers truncates toward zero (so -7 / 2 is -3).
- The expression is always valid, never divides by zero, and every intermediate value fits in a 32-bit signed integer.
Examples
Input: tokens = ["3","4","+","2","*"] Output: 14
This is (3 + 4) * 2.
Input: tokens = ["7","-3","/"] Output: -2
7 / -3 is about -2.33, which truncates toward zero to -2.
Input: tokens = ["10","2","8","*","-"] Output: -6
This is 10 - (2 * 8).
Constraints
- 1 <= len(tokens) <= 10^4
- tokens[i] is "+", "-", "*", "/" or an integer in [-200, 200]
- every intermediate value fits in a 32-bit signed integer
Approaches
- Baseline: reduce the first operator, repeatedly — time O(n²), space O(n)
Follow-up
Turn an ordinary infix expression such as 3 + 4 * (2 - 1) into these tokens first. The shunting-yard algorithm does it with one stack of operators, popping by precedence; feeding its output to this stack evaluates any infix expression in O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
