Evaluate Reverse Polish Notation

01 · Question

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

02 · Analysis

The stack holds values of completed subexpressions. For an operator, pop b first, then a, and push a operator b. Subtraction and division depend on this order. Division truncates toward zero: -7 / 3 becomes -2. Python uses absolute integer division plus a sign correction to avoid float precision loss. The input is a valid expression, divisors are nonzero, and Go intermediates must fit int. O(n) time and O(n) space under constant-time arithmetic.

03 · Solution

Reference solution

1def evalRPN(tokens: list[str]) -> int:
2    stack = []
3    
4    for t in tokens:
5        if t not in {"+", "-", "*", "/"}:
6            stack.append(int(t))
7            continue
8        b = stack.pop()
9        a = stack.pop()
10        if t == "+":
11            stack.append(a + b)
12        elif t == "-":
13            stack.append(a - b)
14        elif t == "*":
15            stack.append(a * b)
16        else:
17            quotient = abs(a) // abs(b)
18            stack.append(-quotient if (a < 0) != (b < 0) else quotient)
19    
20    return stack[-1]

Min Stack

Implement Queue using Stacks