Problem
Evaluate a small stack language. The stack starts empty; integers push values onto its top. Return the final stack from bottom to top. Tokens are separated by spaces and command names are case-insensitive.
Arithmetic +, -, *, / pops the top value as right operand and the next as left operand, then pushes left operator right. Division truncates toward zero. DUP copies the top value; DROP removes it; SWAP exchanges the top two; OVER copies the second-from-top value onto the top.
Define a word with : name body ;. A name contains only letters. The nonempty body may contain integers, built-in commands, and previously defined words. Definitions do not execute their bodies. Redefining a name affects later uses, but older definitions keep the meanings captured when they were defined. A definition may use the previous version of its own name. Nested definitions, forward references, and recursive calls are not allowed.
Every test program is valid: no unknown word, stack underflow, division by zero, or overflow occurs. You do not need to report errors.
Implement mini_stack_language_interpreter(program).
Input
program: The complete valid program.
Output
Return the final stack in bottom-to-top order.
Constraints
0…10,000 tokens. At most 100,000 primitive tokens across all expanded definitions and executed code. Values and intermediate arithmetic fit signed 64-bit. Integer literals use optional minus followed by digits. Tokens : and ; are separate. Built-in names cannot be redefined; user words can be redefined. Empty input returns an empty stack.
Examples
Input:
program = ": square dup * ; 5 square 3 +"
Expected output:
expected = [28]Input:
std::string program = ": square dup * ; 5 square 3 +";
Expected output:
std::vector<long long> expected = {28};Input:
string program = ": square dup * ; 5 square 3 +";
Expected output:
long[] expected = new long[] {28};Explanation
Define square without executing it. Push 5, duplicate it, multiply to get 25, then push 3 and add to obtain 28.
Input:
program = "-7 2 / 9 over"
Expected output:
expected = [-3, 9, -3]Input:
std::string program = "-7 2 / 9 over";
Expected output:
std::vector<long long> expected = {-3, 9, -3};Input:
string program = "-7 2 / 9 over";
Expected output:
long[] expected = new long[] {-3, 9, -3};Explanation
−7 divided by 2 truncates toward zero to −3. Push 9, then OVER copies the second-from-top value, −3.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Treat the program as two intertwined tasks: executing the current stack and remembering what each word meant when it was defined.
Hint 2
Store each user-defined word as a sequence of resolved operations, so later redefinitions do not change earlier bodies.
Hint 3
Watch for definition-time parsing details: capture words by their current meaning, ignore execution inside definitions, and handle case-insensitive built-ins with truncating division.
Expected complexity
O(T) time, O(T) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.