Level 1 Run a stack program
A tiny stack machine keeps a stack of integers (empty at the start) and runs a program written one instruction per line, top to bottom. Write its interpreter:
run(program: str, max_steps=None) -> list[str]
program is the whole text, with lines separated by "\n". max_steps is for level 2: the level-1 tests leave it out. The result is the program's output, one string per printed value.
| Instruction | Values it needs | What it does |
|---|---|---|
PUSH n |
0 | push the integer n |
POP |
1 | remove the top value |
ADD |
2 | pop a (the top), pop b, push b + a |
SUB |
2 | pop a (the top), pop b, push b - a |
DUP |
1 | push a copy of the top value |
SWAP |
2 | swap the top two values |
PRINT |
1 | pop the top value and add it to the output, written in decimal |
Reading lines
- Lines are numbered from 1, and every line counts, blank ones included.
- Words are separated by one or more spaces. Spaces at the start or end of a line don't matter, and a blank line does nothing.
- Instruction names are upper case, exactly as in the table.
nis an optional-followed by one or more digits:7,-12and007are fine;+3,1.5andxare not.
Errors
- The whole program is checked before anything runs. A non-blank line that isn't exactly one of the instructions above (an unknown or lower-case name, a missing or extra word, a bad
n) is a bad instruction. If there is one, nothing runs and the result is["error at line K: bad instruction"], where K is the first bad line. - While running, an instruction that needs more values than the stack holds stops the program. The result is the output so far followed by
"error at line K: stack underflow". - Values still on the stack at the end are ignored.
run("PUSH 3\nPUSH 4\nADD\nDUP\nPRINT\nPUSH 10\nSWAP\nSUB\nPRINT")
# ["7", "3"] (3 + 4 = 7 is printed; then 10 - 7 = 3)
run("PUSH -4\n\n PUSH 6 \nSUB\nPRINT")
# ["-10"] (-4 - 6; the blank line is line 2)
run("PUSH 5\nPRINT\nPRINT\nPUSH 1")
# ["5", "error at line 3: stack underflow"]
run("PUSH 1\nPRINT\n push 2\nPRINT")
# ["error at line 3: bad instruction"] (nothing runs, so nothing is printed)
Programs have at most 10^4 lines. Every n and every value the program computes fits in a signed 64-bit integer.
Ask yourself what the interviewer wants pinned down first: the order of the operands for SUB, whether PRINT removes the value, and whether a bad line stops the program before or after the lines above it have run.