Stack Machine Program
EasyStack · Jane Street
A tiny stack machine works only with 20-bit unsigned integers, i.e. values from 0 to 1048575 (2^20 - 1). It starts with an empty stack and runs the instructions in program in order:
"PUSH x": push the integerx(always within the valid range)."POP": remove the top value."DUP": push a copy of the top value."ADD": pop the top valueb, then popa, and pusha + b."SUB": pop the top valueb, then popa, and pusha - b."MUL": pop the top valueb, then popa, and pusha * b.
The machine fails, and stops immediately, if:
- an instruction needs more values than the stack currently holds, or
ADD,SUBorMULproduces a result below0or above1048575.
Return the value on top of the stack after the whole program has run. Return -1 if the machine failed or if the stack is empty at the end.
Example 1
- Input:
- program = ["PUSH 4", "PUSH 6", "DUP", "MUL", "PUSH 5", "SUB", "ADD"]
- Output:
- 35
- Explanation
- The stack goes
[4, 6],[4, 6, 6], thenMULgives[4, 36]. Pushing 5 and subtracting gives36 - 5 = 31, andADDleaves[35].
Example 2
- Input:
- program = ["PUSH 3", "PUSH 5", "SUB"]
- Output:
- -1
- Explanation
SUBcomputes3 - 5 = -2, which is below the valid range, so the machine fails.
Example 3
- Input:
- program = ["PUSH 1024", "DUP", "MUL"]
- Output:
- -1
- Explanation
1024 * 1024 = 1048576, one more than the largest allowed value, so the machine fails.
Constraints
1 <= program.length <= 10^5- Every instruction is one of the six forms above, with a single space after
PUSH 0 <= x <= 1048575for everyPUSH x