stack_cpu.md

Implement a minimal stack-based CPU. The CPU doesn’t store numbers directly — it stores instructions. Each instruction changes a single accumulator register ACC, starting at 0.

You must support these instructions:

• PUSH ADD n -> means “when executed, do ACC = ACC + n”
• PUSH SUB n -> means “when executed, do ACC = ACC - n”
• POP -> removes the last pushed instruction (undo it)
• ACC() -> returns current accumulator value in O(1)

Key requirement:

• ACC() must be O(1).

So you need to update ACC as instructions are pushed/popped, not re-run the whole program each time.

API

type Op = "ADD" | "SUB";
class StackCPU {
  push(op: Op, n: number): void;
  pop(): { op: Op; n: number } | null;
  acc(): number;
}

Example Trace

cpu.push("ADD", 1)   // stack: [ADD 1]        ACC = 1
cpu.push("ADD", 2)   // stack: [ADD 1, ADD 2] ACC = 3
cpu.push("SUB", 5)   // stack: [..., SUB 5]   ACC = -2
cpu.acc() -> -2
cpu.pop() -> { op:"SUB", n:5 }  // undo SUB 5
// stack: [ADD 1, ADD 2] ACC = 3
cpu.acc() -> 3
cpu.push("SUB", 1)   // ACC = 2
cpu.acc() -> 2

Constraints

• Integers may be negative too.
• Up to 1e6 ops → recomputing ACC from scratch is not allowed.
• pop on empty should return null, not explode.