Compilers: A whole tiny compiler

Put the phases together: lex, parse, generate stack code, then run it.

What to build

A program that compiles an arithmetic expression to stack-machine code, prints the code, and runs it.

Requirements

  • Print one instruction per line: PUSH n, ADD, SUB, MUL or DIV, in the order a post-order walk of the tree gives.
  • Operators group from the left, and * and / bind tighter than + and −. Finish with result R (division rounds down).

Input

One line: an arithmetic expression with whole numbers, operators, brackets and spaces.

Output

The code, then result R.

Constraints

At most 60 characters; the expression is valid and never divides by zero.

Example

Input:

2 + 3 * (4 - 1)

Output:

PUSH 2
PUSH 3
PUSH 4
PUSH 1
SUB
MUL
ADD
result 11

Why it works

Visiting the tree in post-order emits each operation after both of its operands, which is exactly the order a stack machine needs.

Examples

Example 1 · Input
2 + 3 * (4 - 1)
Expected output
PUSH 2
PUSH 3
PUSH 4
PUSH 1
SUB
MUL
ADD
result 11
Example 2 · Input
8 - 3 - 2
Expected output
PUSH 8
PUSH 3
SUB
PUSH 2
SUB
result 3

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

Hints

Hint 1

Parse with one function per level (expr for + −, term for * /, factor for numbers and brackets), building tuples.

Hint 2

Generate code by visiting the left subtree, then the right, then emitting the operation.

Solution

Show one correct solution (try it yourself first)
import re

tokens = re.findall(r"\d+|[-+*/()]", input())
pos = 0


def peek():
    return tokens[pos] if pos < len(tokens) else None


def take():
    global pos
    pos += 1
    return tokens[pos - 1]


def expr():
    node = term()
    while peek() in ("+", "-"):
        node = (take(), node, term())
    return node


def term():
    node = factor()
    while peek() in ("*", "/"):
        node = (take(), node, factor())
    return node


def factor():
    if peek() == "(":
        take()
        node = expr()
        take()
        return node
    return int(take())


NAMES = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}
code = []


def gen(node):
    if isinstance(node, int):
        code.append(f"PUSH {node}")
    else:
        op, left, right = node
        gen(left)
        gen(right)
        code.append(NAMES[op])


gen(expr())
stack = []
for ins in code:
    print(ins)
    if ins.startswith("PUSH"):
        stack.append(int(ins.split()[1]))
    else:
        b, a = stack.pop(), stack.pop()
        stack.append({"ADD": a + b, "SUB": a - b, "MUL": a * b, "DIV": a // b}[ins])
print("result", stack.pop())

Lesson: How a compiler works →