DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Evaluate Reverse Polish Notation

mediumStack and queue Must-do

Problem statement

An arithmetic expression is given as a list of string tokens in postfix (Reverse Polish) order: each operator comes after its two operands, so no brackets are ever needed. Tokens are either integers (possibly negative) or one of +, -, *, /.

Evaluate the expression and return the result as an integer. Division between two integers truncates toward zero, so -7 / 2 is -3, not -4. You can assume the expression is well formed and never divides by zero.

Examples

Example 1

Input: tokens = ["3", "4", "+", "2", "*"]

Output: 14

Explanation: 3 + 4 = 7, then 7 * 2 = 14. In ordinary notation this is (3 + 4) * 2.

Example 2

Input: tokens = ["20", "-6", "/", "5", "+"]

Output: 2

Explanation: 20 / -6 is -3.33, which truncates toward zero to -3. Then -3 + 5 = 2.

Hints

Approach

Postfix notation was designed for a stack.

  1. Walk the tokens once.
  2. A number is pushed onto the stack.
  3. An operator pops the top value as the right operand b, then the next value as the left operand a, and pushes a op b.
  4. At the end the stack holds exactly one value: the answer.

For division, Python's // floors toward negative infinity, so use int(a / b) to truncate toward zero. Java's / on int already truncates toward zero.

ComplexityTime O(n)Space O(n)
Python
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
stack = []
for t in tokens:
if t in ("+", "-", "*", "/"):
b = stack.pop() # right operand comes off first
a = stack.pop()
if t == "+":
stack.append(a + b)
elif t == "-":
stack.append(a - b)
elif t == "*":
stack.append(a * b)
else:
stack.append(int(a / b)) # truncate toward zero, not floor
else:
stack.append(int(t))
return stack[0]

Follow-up questions

  • Convert an ordinary infix expression like (3 + 4) * 2 into postfix first (the shunting-yard algorithm).
  • Report a clear error instead of crashing when the expression is malformed, for example ["1", "+"].

Frequently asked questions

Addition and multiplication do not care, but a - b and a / b do. The value popped first was pushed last, so it is the right-hand operand. Swapping them is the most common bug in this problem.

// rounds toward negative infinity, so -7 // 2 is -4. The problem wants truncation toward zero, which is -3. int(a / b) gives that for the value ranges used here.

Any small expression evaluator, such as a threshold rule in an alerting config or a calculator in a CLI tool, ends up turning the expression into postfix and evaluating it with a stack. Stack-based virtual machines and some older monitoring tools work the same way.