ML Prep

Evaluate postfix arithmetic with a stack

Problem

Implement evaluate_postfix(tokens) for a valid postfix expression whose tokens are integer literals or +, -, and *. For an operator, pop the right operand and then the left operand. Return the final integer.

Reveal answer or reference solution

Push integers. For an operator, pop right, pop left, compute left operator right, and push the result. Subtraction makes the pop order observable. The algorithm is O(n)O(n) time and O(n)O(n) worst-case space.

def evaluate_postfix(tokens: list[str]) -> int:
    stack: list[int] = []
    for token in tokens:
        if token not in {"+", "-", "*"}:
            stack.append(int(token))
            continue
        right = stack.pop()
        left = stack.pop()
        if token == "+":
            stack.append(left + right)
        elif token == "-":
            stack.append(left - right)
        else:
            stack.append(left * right)
    return stack[0]

Public tests

  • evaluate_postfix(["2", "3", "+"]) → 5
  • evaluate_postfix(["7", "2", "-"]) → 5
  • evaluate_postfix(["2", "3", "+", "4", "*"]) → 20
  • evaluate_postfix(["5"]) → 5
Outcome

Previous attempts

Loading attempts saved in this browser…

    Review Screening Results