Simulate a Stack from Push, Pop and End-of-Input Commands

Simulate a stack driven by a stream of text commands and report what it outputs. The commands arrive as one string of whitespace-separated tokens:

• U num: push the integer num onto the stack.
• O: pop the top value off the stack and output it.
• X: the input stream has ended.

Return the output values in the order they were popped.

Function Signature

def simulate_stack(commands: str) -> list[int]:

Rules

• Tokens are separated by one or more whitespace characters (spaces or newlines).
• U is always followed by exactly one integer token, written in decimal with an optional leading -.
• Each O removes the current top value and appends it to the output.
• X appears exactly once, as the last token. Values still on the stack when X is reached are not output.
• The original prompt printed the popped values separated by spaces, so the printed output -3 3 corresponds to the return value [-3, 3].

Constraints

• The input has between 1 and 200,000 tokens.
• -10^9 <= num <= 10^9
• Every O is issued while the stack is non-empty.

Examples

Example 1

Input:  commands = "U 3 U -3 O O X"
Output: [-3, 3]

3 is pushed, then -3. The first O pops -3 and the second pops 3.

Example 2

Input:  commands = "U 5 U 7 O U 2 X"
Output: [7]

Only one pop happens. 5 and 2 are still on the stack at X, so they are not output.

Example 3

Input:  commands = "X"
Output: []

The stream ends before any command runs.

Stack Simulator Driven by Text Commands

Simulate a stack driven by a stream of text commands and report what it outputs.

You are given one string commands made of tokens separated by one or more whitespace characters (spaces or newlines). The commands are:

• U num: push the integer num onto the stack. U is always followed by exactly one integer token, written in decimal with an optional leading -.
• O: pop the top value off the stack and output it (append it to the output).
• X: the input stream has ended. X appears exactly once, as the last token.

Values still on the stack when X is reached are not output. Return the output values, as a list of integers, in the order they were popped. If nothing is popped, return an empty list. (The original prompt printed the popped values separated by spaces, so the printed output -3 3 corresponds to the return value [-3, 3].)

Every value satisfies -10^9 <= num <= 10^9, so every pushed and output value fits in a signed 32-bit integer; no value can exceed 2^31-1.

Example 1

Input:  commands = "U 3 U -3 O O X"
Output: [-3, 3]

3 is pushed, then -3. The first O pops -3 and the second pops 3.

Example 2

Input:  commands = "U 5 U 7 O U 2 X"
Output: [7]

Only one pop happens. 5 and 2 are still on the stack at X, so they are not output.

Constraints

• The input has between 1 and 200,000 tokens.
• -10^9 <= num <= 10^9
• Every O is issued while the stack is non-empty.
• X appears exactly once, as the last token.
• Tokens are separated by one or more whitespace characters (spaces or newlines).

Hints

1. Two neighbouring tokens can be separated by several spaces or newlines, so break the input on runs of whitespace rather than on a single space character.
2. A U token is never meaningful on its own: the token right after it is the value to store.
3. Each O reports the most recently stored value that has not been reported yet, and anything still stored when X arrives is never reported.

Approach

Algorithm: split the command string on runs of whitespace (any mix of spaces and newlines) to get the token sequence, then scan it once while keeping a dynamic array as the stack. A U token consumes the following token, parses it as a signed decimal integer and appends it to the array; an O removes the last element of the array and appends it to the output list; X stops the scan.

Invariant: after any prefix of tokens has been processed, the array holds exactly the values that were pushed and not yet popped, in push order (top at the end), and the output list holds every popped value in pop order.

Correctness: a stack pop must return the most recently pushed value that has not been removed yet, which by the invariant is the last array element, so each O appends exactly the value the specification requires and keeps the invariant. X is the last token, so stopping there processes every command; values still in the array are never appended, matching the rule that values left on the stack are not output.

Edge cases: "X" alone returns []; a push-only stream returns []; multiple spaces or newlines between tokens produce no empty tokens because splitting is on whitespace runs; a leading - is part of the integer token. The constraint that every O hits a non-empty stack means no empty-pop handling is needed. All values lie in [-10^9, 10^9], so 32-bit integers suffice in every language.

• Time complexity: O(L), where L is the length of commands
• Space complexity: O(L)