Evaluate Reverse Polish Notation

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.evalRPN(tokens). Tokens are integer strings or +, -, *, /. Apply binary operators to the two most recent operands; division truncates toward zero.

Starter code

class Solution:
    def evalRPN(self, tokens):
        pass

Test cases

mixed

{
  "args": [
    [
      "2",
      "1",
      "+",
      "3",
      "*"
    ]
  ]
}

Expected: 9

Wizard outline

Step 1: Initialize Solution.evalRPN
Replace the empty starter with the first real state owned by Solution.evalRPN. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Mixed case
Complete the readable core algorithm for one representative Interview case. Pop right operand before left operand and push each intermediate result.
Step 4: Harden the Negative Division boundary
Repair the reviewed boundary and pass the complete submission contract. The stack holds exactly the evaluated values of unfinished postfix subexpressions. Each operator replaces its two immediately preceding operand expressions with their correct combined value, leaving the final expression value alone on the stack.

Footguns and prerequisites

Python // rounds negative quotients downward, while this problem requires truncation toward zero.
python specific rapid fire

Reviewed references

LeetCode 150 — Evaluate Reverse Polish Notation

Practice prerequisites

Apply One Stack Reduction(opens in a new tab)
Apply One Stack Reduction isolates the stack is the fully reduced form of the processed prefix and contains no adjacent equal pair. That focused state discipline is required when implementing evaluate reverse polish notation as a complete Interview Problem.

Recommended approach and implementation

Push integers. For an operator, pop right then left, compute the operation, and push its result; convert division with int(left/right).

Why it works: The stack holds exactly the evaluated values of unfinished postfix subexpressions. Each operator replaces its two immediately preceding operand expressions with their correct combined value, leaving the final expression value alone on the stack.

class Solution:
    def evalRPN(self, tokens):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        stack = []
        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)
            elif token == '*':
                stack.append(left * right)
            else:
                stack.append(int(left / right))
        return stack[-1]