Simulate a Stack from Push, Pop and End-of-Input Commands
Company: Wex
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
Input: commands = "X"
Output: []
```
The stream ends before any command runs.
Overview: A coding problem that simulates a stack from a stream of text commands: push an integer, pop and output the top value, or end the input. It tests careful token parsing, signed integers and returning the popped values in the order they were removed.
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**
```text
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**
```text
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).
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.
- U is always followed by exactly one integer token, written in decimal with an optional leading '-'.
- X appears exactly once, as the last token.
- Tokens are separated by one or more whitespace characters (spaces or newlines).
Examples
Input: ('X',)
Expected Output: []
Explanation: Minimum valid stream: X alone ends the input before any command runs, so nothing is output.
Input: ('U 42 X',)
Expected Output: []
Explanation: Singleton push that is still on the stack at X is not output.
Hints
- 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.
- A `U` token is never meaningful on its own: the token right after it is the value to store.
- Each `O` reports the most recently stored value that has not been reported yet, and anything still stored when `X` arrives is never reported.