DSA Evaluating Reverse Polish Notation

The problem

Reverse Polish Notation is a way of writing arithmetic. Each operator follows its two numbers. The expression 3 4 + means 3 + 4, and its value is 7.

The input is a list of tokens. A token is one piece of the expression, either a number or an operator. The output is one integer, the value of the whole expression.

Division is integer division. It truncates toward zero. So -7 divided by 2 is -3 here, not -4.

cases = [
    (["2", "1", "+", "3", "*"], 9),
    (["10", "2", "/", "3", "+"], 8),
    (["5", "1", "2", "+", "4", "*", "+", "3", "-"], 14),
    (["-7", "2", "/"], -3),
]
for tokens, expected in cases:
    print("tokens", " ".join(tokens), "value:", expected)

Read one row at a time. The first row groups as (2 + 1) * 3, which is 9. The last row is the negative-division case: -7 / 2 truncates toward zero and gives -3.

Intuition: the infix habit is the trap

The first idea is to read the tokens the infix way. Infix is the usual school form, with the operator between its numbers. That reading scans for an operator first, then hunts for the numbers around it.

The scan is the trap. An operator in this notation belongs to the two numbers just before it, not to numbers on both sides. A scan that grabs neighbouring tokens in list order can pair an operator with the wrong numbers.

tokens = ["2", "1", "+", "3", "*"]
for i, token in enumerate(tokens):
    if token in "+-*/":
        print("operator", token, "at index", i, "neighbours:", tokens[i - 1], "and", tokens[i + 1] if i + 1 < len(tokens) else "none")

The plus at index 2 sits between 1 and 3 in the list. Its real operands are 2 and 1, the two values that came before it. The star has no right neighbour at all. Position in the list is the wrong guide; order of arrival is the right one.

Brute force: rewrite the token list

A straightforward method works on the list itself. Find the first operator. Replace it and the two numbers before it with the single result. Then start the scan again from the top.

The method is correct. Each rewrite shrinks the list by two tokens. The cost is the restarting: early tokens are scanned again after every rewrite.

def apply_op(a, token, b):
    if token == "+":
        return a + b
    if token == "-":
        return a - b
    if token == "*":
        return a * b
    return int(a / b)

def evaluate_slow(tokens):
    tokens = list(tokens)
    scans = 0
    while len(tokens) > 1:
        for i, token in enumerate(tokens):
            scans += 1
            if token in "+-*/":
                result = apply_op(int(tokens[i - 2]), token, int(tokens[i - 1]))
                tokens[i - 2:i + 1] = [str(result)]
                break
    return int(tokens[0]), scans

for tokens in (["2", "1", "+", "3", "*"], ["5", "1", "2", "+", "4", "*", "+", "3", "-"]):
    value, scans = evaluate_slow(tokens)
    print(" ".join(tokens), "->", value, "scanned tokens:", scans)

The nine-token expression costs 21 scanned tokens. The count grows fast because each of the four rewrites restarts the scan. A single left-to-right pass would visit each token once.

The optimal solution: one stack, one pass

Keep a stack of waiting numbers: push each number, and let each operator pop the top two, combine them, and push the result. That one sentence is the whole solution.

Order matters on the pop. The first value popped is the right side of the operation. The second value popped is the left side. Swapping them breaks minus and divide.

def evaluate(tokens):
    stack = []
    for token in tokens:
        if token in "+-*/":
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    return stack[0]

cases = [
    (["2", "1", "+", "3", "*"], 9),
    (["10", "2", "/", "3", "+"], 8),
    (["5", "1", "2", "+", "4", "*", "+", "3", "-"], 14),
    (["-7", "2", "/"], -3),
]
for tokens, expected in cases:
    print(" ".join(tokens), "->", evaluate(tokens), "expected:", expected)

All four cases pass. The negative-division case gives -3 because int(a / b) drops the fraction toward zero. Python floor division would give -4 there instead.

Walkthrough: 5 1 2 + 4 * + 3 -

Watch the stack on the longest case. A number token grows the stack by one. An operator token shrinks it by one, replacing two values with one result.

def evaluate_traced(tokens):
    stack = []
    for token in tokens:
        if token in "+-*/":
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                result = a + b
            elif token == "-":
                result = a - b
            elif token == "*":
                result = a * b
            else:
                result = int(a / b)
            stack.append(result)
        else:
            stack.append(int(token))
        print("token", token, "-> stack", stack)
    return stack[0]

print("answer:", evaluate_traced(["5", "1", "2", "+", "4", "*", "+", "3", "-"]))

The plus at step four makes 3 from 1 and 2. The star then makes 12 from that 3 and the 4. One value remains at the end, and it is the answer: 14.

Complexity

Time is O(n) for n tokens: the stack version visits each token once, and each visit does a fixed amount of work.

Space is O(n) in the worst case: a run of number tokens can fill the stack before any operator arrives.

def visits_stack(tokens):
    return len(tokens)

def visits_slow(tokens):
    tokens = list(tokens)
    scans = 0
    while len(tokens) > 1:
        for i, token in enumerate(tokens):
            scans += 1
            if token in "+-*/":
                a, b = int(tokens[i - 2]), int(tokens[i - 1])
                result = a + b if token == "+" else a - b if token == "-" else a * b if token == "*" else int(a / b)
                tokens[i - 2:i + 1] = [str(result)]
                break
    return scans

for size in (5, 9, 17):
    tokens = ["1"] * (size // 2 + 1) + ["+"] * (size // 2)
    print("tokens:", size, "stack visits:", visits_stack(tokens), "rewrite scans:", visits_slow(tokens))

The stack count equals the token count at every size. The rewrite count pulls away as the expression grows. That gap, not a clock, is the evidence.

Edge cases and pitfalls

A single number token is a complete expression. No operator ever runs, and the stack returns the number itself.

The pop order is the classic pitfall. Popping into a then b and computing a - b silently reverses every minus and divide. The names in the solution keep the deeper value as the left side.

def evaluate(tokens):
    stack = []
    for token in tokens:
        if token in "+-*/":
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    return stack[0]

print("single token:", evaluate(["42"]))
print("negative result:", evaluate(["3", "4", "-"]))
print("divide -7 by 2:", evaluate(["-7", "2", "/"]))
print("divide 7 by -2:", evaluate(["7", "-2", "/"]))
print("divide 6 by 4:", evaluate(["6", "4", "/"]))

Both mixed-sign divisions truncate toward zero. Each gives -3, where floor division would give -4. The last line shows the same rule on a positive value: 6 / 4 is 1.5, which truncates to 1.