progress

~/problems / Iterators & parsers / Parsers and interpreters

Stack machine interpreter

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 3 levels ~60 min Jane Street

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. n is an optional - followed by one or more digits: 7, -12 and 007 are fine; +3, 1.5 and x are 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.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Parsers and interpreters. Tokenize, recursive descent, S-expressions, evaluation and type inference.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc