Evaluate a Small Stack-Based Integer Language

Problem Statement

You are tasked with building a lightweight interpreter for a stack-based integer language. The program is provided as a string of whitespace-separated tokens and is executed from left to right.

The interpreter maintains an internal integer stack and an output list. It supports the following operations:

• Integer Literals: An optional leading sign (+ or -) followed by one or more digits (e.g., 42, -7, +0). Pushes the integer onto the stack.
• +: Pops b, then pops a. Pushes a + b.
• -: Pops b, then pops a. Pushes a - b.
• *: Pops b, then pops a. Pushes a * b.
• /: Pops b, then pops a. Pushes int(a / b) (integer division truncated toward zero).
• DUP: Duplicates the top value on the stack.
• POP: Removes and discards the top value from the stack.
• PRINT: Pops the top value from the stack and appends it to the output list.

Error Handling

If an error occurs, execution terminates immediately. Any outputs collected in the output list before the error must be preserved.

The possible error strings are:

• "UNDERFLOW": An operation requires more operands than currently exist on the stack.
• "ZERODIVISION": A division operator / encounters a divisor b == 0.
• "INVALID_TOKEN": A token is encountered that cannot be parsed as a known command or integer.

Function Signature

def evaluate_stack_program(program: str) -> tuple[list[int], str | None]:
    """
    Evaluates the stack program.
    Returns a tuple of (output_list, error_code).
    If the program finishes without errors, error_code is None.
    """
    pass

Examples

Example 1:

program = "10 4 - PRINT"
# '10' -> stack: [10]
# '4'  -> stack: [10, 4]
# '-'  -> pops 4, 10; pushes 10 - 4 = 6; stack: [6]
# 'PRINT' -> pops 6; output: [6]; stack: []
# Result: ([6], None)

Example 2:

program = "7 PRINT 5 0 / PRINT"
# '7'     -> stack: [7]
# 'PRINT' -> output: [7]; stack: []
# '5'     -> stack: [5]
# '0'     -> stack: [5, 0]
# '/'     -> division by zero error!
# Result: ([7], "ZERODIVISION")

Example 3:

program = "3 DUP * PRINT POP"
# '3'     -> stack: [3]
# 'DUP'   -> stack: [3, 3]
# '*'     -> pops 3, 3; pushes 9; stack: [9]
# 'PRINT' -> output: [9]; stack: []
# 'POP'   -> stack is empty! Underflow error.
# Result: ([9], "UNDERFLOW")

Constraints

• 0 <= len(program) <= 10^4
• Tokens are separated by one or more whitespace characters. An empty or whitespace-only program produces ([], None).
• All numerical values fit within standard 64-bit signed integers.