The Postfix Processor

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

Our calculator service receives each expression as a list of string tokens in well-formed postfix (RPN) order: integer literals, which can be negative, and the operators +, -, * and /. Return the expression's integer value, with division dropping any fractional part toward zero.

Math without parentheses - the operators come after the numbers.

Example 1

Input:

tokens = ["2","1","+","3","*"]

Output:

9

Example 2

Input:

tokens = ["4","13","5","/","+"]

Output:

6

Worked solution and explanation

This is bookkeeping of pending values dressed up as a calculator. In postfix, every operator consumes the two most recent values still waiting and leaves its result in their place, so the whole job is knowing which values are waiting and in what order. Anyone can write the loop. What separates candidates is three small decisions inside it: the later value is the right-hand side, / truncates toward zero instead of flooring, and '-4' is a number, not a minus sign. Miss one and '10 4 -' comes back as -6, '2 9 - 4 /' as -2, or a negative literal crashes the run.

Walking it

Step 1: Keep waiting values in arrival order

Every literal goes onto the end of operands as an int. Nothing ever happens in the middle of that list: an operator only touches the last two entries, so appending at the end and reading operands[-1] and operands[-2] is all the bookkeeping the problem needs.

Step 2: Read the right-hand side first

When an operator arrives, operands[-1] is the value that arrived later, so it is the right side and operands[-2] is the left. For '+' and '*' the order is invisible, which is exactly why a swapped version passes the first example and then fails '10 4 -'.

Step 3: Collapse two values into one

Drop the last entry and overwrite the new last entry with the result. The list shrinks by one per operator, and for a well-formed expression it ends holding exactly one value: the answer, which is why operands[0] is returned.

Step 4: Divide toward zero

int(left / right) takes the true quotient and drops its fraction, which moves toward zero for either sign. left // right floors: it agrees for positive results and disagrees on every negative quotient that has a remainder.

Postfix evaluation
def apply_operator(operator, left, right):
    if operator == '+':
        result = left + right
    elif operator == '-':
        result = left - right
    elif operator == '*':
        result = left * right
    else:
        # int() of the true quotient drops the fraction toward zero; // would floor
        result = int(left / right)
    return result


def evaluate_expression(tokens: list) -> int:
    operands = []
    for token in tokens:
        if token in ['+', '-', '*', '/']:
            right = operands[-1]
            left = operands[-2]
            del operands[-1]
            operands[-1] = apply_operator(token, left, right)
        else:
            operands.append(int(token))
    return operands[0]
Flooring with `left // right`
'2 9 - 4 /' reaches -7 and then divides by 4. -7 // 4 is -2, because floor moves to the next lower integer.
Truncating with `int(left / right)`
int(-7 / 4) is int(-1.75), which is -1: the fraction is dropped and the value moves toward zero, matching the expected answer.

Common follow-up questions