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,MULorDIV, 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
2 + 3 * (4 - 1)
PUSH 2 PUSH 3 PUSH 4 PUSH 1 SUB MUL ADD result 11
8 - 3 - 2
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())