Problema
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.
Vincoli
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.
Esempi
Input:
program = ": square dup * ; 5 square 3 +"
Output atteso:
expected = [28]Input:
std::string program = ": square dup * ; 5 square 3 +";
Output atteso:
std::vector<long long> expected = {28};Input:
string program = ": square dup * ; 5 square 3 +";
Output atteso:
long[] expected = new long[] {28};Spiegazione
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"
Output atteso:
expected = [-3, 9, -3]Input:
std::string program = "-7 2 / 9 over";
Output atteso:
std::vector<long long> expected = {-3, 9, -3};Input:
string program = "-7 2 / 9 over";
Output atteso:
long[] expected = new long[] {-3, 9, -3};Spiegazione
−7 divided by 2 truncates toward zero to −3. Push 9, then OVER copies the second-from-top value, −3.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Pensa al programma come a due compiti intrecciati: eseguire lo stack corrente e ricordare cosa significava ogni parola quando è stata definita.
Suggerimento 2
Memorizza ogni parola definita dall'utente come una sequenza di operazioni risolte, così le ridefinizioni successive non cambiano i corpi già salvati.
Suggerimento 3
Fai attenzione al parsing in fase di definizione: cattura le parole secondo il loro significato attuale, ignora l'esecuzione dentro le definizioni e gestisci i built-in senza distinzione tra maiuscole e minuscole con divisione troncata.
Complessità attesa
tempo O(T), spazio aggiuntivo O(T)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.