Compilers: A virtual machine with jumps

Run stack-machine code with variables and jumps.

What to build

A program that runs stack bytecode and prints what it outputs.

Requirements

  • Instructions (addresses start at 0): PUSH n, LOAD x, STORE x, ADD, SUB, MUL, DIV (rounds down), LESS, EQUAL (push 1 or 0), JUMP a, JUMP_IF_FALSE a (pop a value and jump if it is 0), PRINT (pop and print).
  • Variables start at 0. Run from address 0 until the program counter passes the last instruction.

Input

Line 1: n. Then n instructions.

Output

The printed values, one per line.

Constraints

n ≤ 100; programs stop within 10,000 steps and never divide by zero or pop an empty stack.

Example

Input:

11
PUSH 3
STORE n
LOAD n
JUMP_IF_FALSE 11
LOAD n
PRINT
LOAD n
PUSH 1
SUB
STORE n
JUMP 2

Output:

3
2
1

Why it works

The program counter is the only thing that decides what runs next, so jumps are just assignments to it.

Examples

Example 1 · Input
11
PUSH 3
STORE n
LOAD n
JUMP_IF_FALSE 11
LOAD n
PRINT
LOAD n
PUSH 1
SUB
STORE n
JUMP 2
Expected output
3
2
1
Example 2 · Input
4
PUSH 2
PUSH 5
MUL
PRINT
Expected output
10

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Keep a program counter; fetch the instruction at pc, add one to pc, then carry the instruction out.

Hint 2

For SUB, DIV, LESS and EQUAL, pop b first and then a, and push a op b.

Solution

Show one correct solution (try it yourself first)
code = [input().split() for _ in range(int(input()))]
stack, memory, pc = [], {}, 0
while pc < len(code):
    op, *arg = code[pc]
    pc += 1
    if op == "PUSH":
        stack.append(int(arg[0]))
    elif op == "LOAD":
        stack.append(memory.get(arg[0], 0))
    elif op == "STORE":
        memory[arg[0]] = stack.pop()
    elif op == "PRINT":
        print(stack.pop())
    elif op == "JUMP":
        pc = int(arg[0])
    elif op == "JUMP_IF_FALSE":
        if stack.pop() == 0:
            pc = int(arg[0])
    else:
        b, a = stack.pop(), stack.pop()
        if op == "ADD":
            stack.append(a + b)
        elif op == "SUB":
            stack.append(a - b)
        elif op == "MUL":
            stack.append(a * b)
        elif op == "DIV":
            stack.append(a // b)
        elif op == "LESS":
            stack.append(int(a < b))
        else:
            stack.append(int(a == b))

Lesson: Generating code for a stack machine →