# The Postfix Processor

> Math without parentheses - the operators come after the numbers.

Canonical URL: <https://datadriven.io/problems/the_postfix_processor>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of string tokens forming a valid postfix (RPN) expression supporting integers and operators '+', '-', '*', '/', evaluate it. Use integer-truncation-toward-zero division for '/'. Return the integer result.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **stack-based expression evaluation**, a fundamental pattern in compilers and calculators. It checks whether candidates understand postfix notation and can implement the operand-push, operator-pop-and-apply pattern cleanly.

---

### Break down the requirements

#### Step 1: Push operands onto the stack

When the token is a number, convert it to an integer and push it.

#### Step 2: Pop two operands on operator tokens

When the token is an operator, pop the top two values. The second popped value is the left operand.

#### Step 3: Apply the operator and push the result

Compute the result of the operation and push it back onto the stack.

#### Step 4: Handle integer division toward zero

Python's `//` operator truncates toward negative infinity, but the problem requires truncation toward zero. Use `int(a / b)` instead.

---

### The solution

**Stack-based postfix evaluation**

```python
def eval_postfix(tokens):
    stack = []
    operators = {'+', '-', '*', '/'}
    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    result = stack[0]
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of tokens. Each token is processed once.
> 
> **Space:** O(n) for the stack in the worst case.

> **Interviewers Watch For**
>
> Do you get the operand order right? The first pop is the right operand, the second is the left. `a - b` is not the same as `b - a`. This is the most common bug.

> **Common Pitfall**
>
> Using Python's `//` for division. `-7 // 2` gives `-4` in Python, but truncation toward zero should give `-3`. Use `int(-7 / 2)` to get `-3`.

---

## Common follow-up questions

- How would you convert infix to postfix? _(Tests the Shunting Yard algorithm with operator precedence.)_
- What if you needed to support parentheses? _(Tests that postfix notation does not need parentheses by design.)_
- How would you handle division by zero? _(Tests adding error handling for edge cases.)_
- What if tokens could include unary operators like negation? _(Tests distinguishing unary minus from binary minus during parsing.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_postfix_processor)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.