Stack Machine Interpreter with Typed Int and String Values
Company: Jane Street
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are building an interpreter for a simple stack machine. The machine has a single stack, and every value on the stack is one of exactly two primitive types:
- an **integer** (e.g., `7`), or
- a **string** (e.g., `"7"`).
The integer `7` and the string `"7"` are **different values** and must never be conflated. Your value representation must preserve this type distinction at all times.
The machine executes a sequence of parsed instructions, one at a time, against the same persistent stack. There are four instruction kinds:
1. `PUSH v` — push the value `v` onto the stack. The operand `v` is either an integer or a string, and its type is known at parse time.
2. `POP` — remove the top value from the stack and discard it.
3. `POP_AND_PRINT` — remove the top value from the stack and print it to standard output on its own line. An integer is printed in its usual decimal form; a string is printed as its raw characters (no surrounding quotes).
4. `ADD` — pop the top two values from the stack, combine them, and push the result back onto the stack:
- If **both** values are integers, push their integer **sum**.
- If **at least one** value is a string, convert any integer operand to its decimal string representation and push the **concatenation**. The value that was **deeper** in the stack (pushed earlier) comes first in the concatenated result, followed by the value that was on top.
Implement a function `operate(instruction)` that applies one instruction to the machine's stack, and use it to process an entire program (a list of instructions in order). You may design the parsed-instruction representation however you like, but it must carry both the operation and, for `PUSH`, a typed operand that distinguishes integers from strings — including in languages where a single variable cannot naturally hold "int or string."
## Input
A program given as a list of instructions, in execution order. In the textual form, one instruction appears per line:
- `PUSH 7` pushes the integer `7` (operand written without quotes).
- `PUSH "7"` pushes the string `7` (operand written in double quotes).
- `POP`, `POP_AND_PRINT`, and `ADD` take no operand.
## Output
The values printed by each `POP_AND_PRINT`, one per line, in execution order. If the program prints nothing, output nothing.
## Example
Input:
```
PUSH 7
PUSH 7
ADD
POP_AND_PRINT
PUSH 7
PUSH "7"
ADD
POP_AND_PRINT
PUSH "ab"
PUSH "cd"
ADD
POP_AND_PRINT
```
Output:
```
14
77
abcd
```
Explanation:
- `7 + 7` is int + int, so integer addition gives `14`.
- `7 + "7"` involves a string, so the integer `7` becomes the string `7` and concatenation gives the string `77` (not the integer `14`).
- `"ab" + "cd"` concatenates to `abcd`; the earlier-pushed value (`ab`) comes first.
## Constraints
- $1 \le$ number of instructions $\le 10^5$.
- Integer operands and all intermediate integer sums fit in a signed 64-bit integer.
- String operands consist of printable ASCII characters, may be empty, and may contain digit characters (a string of digits is still a string).
- The total length of all string values ever created during execution does not exceed $10^6$ characters.
- The program is guaranteed to be valid: `POP` and `POP_AND_PRINT` are only issued when the stack is non-empty, and `ADD` is only issued when the stack holds at least two values.