Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Mini Stack-Language Interpreter

Evaluate a small stack language.

Das lernst du

  • Eine kleine Sprache in Tokens zerlegen
  • Befehle mit einem Stack ausführen
  • Fehler für ungültige Programme melden

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.

Einschränkungen

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.

Beispiele

Beispiel 1
Eingabe:
program = ": square dup * ; 5 square 3 +"

Erwartete Ausgabe:
expected = [28]
Eingabe:
std::string program = ": square dup * ; 5 square 3 +";

Erwartete Ausgabe:
std::vector<long long> expected = {28};
Eingabe:
string program = ": square dup * ; 5 square 3 +";

Erwartete Ausgabe:
long[] expected = new long[] {28};

Erläuterung

Define square without executing it. Push 5, duplicate it, multiply to get 25, then push 3 and add to obtain 28.

Beispiel 2
Eingabe:
program = "-7 2 / 9 over"

Erwartete Ausgabe:
expected = [-3, 9, -3]
Eingabe:
std::string program = "-7 2 / 9 over";

Erwartete Ausgabe:
std::vector<long long> expected = {-3, 9, -3};
Eingabe:
string program = "-7 2 / 9 over";

Erwartete Ausgabe:
long[] expected = new long[] {-3, 9, -3};

Erläuterung

−7 divided by 2 truncates toward zero to −3. Push 9, then OVER copies the second-from-top value, −3.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Behandle das Programm als zwei miteinander verflochtene Aufgaben: den aktuellen Stack ausführen und merken, was jedes Wort bei seiner Definition bedeutete.

Hinweis 2

Speichere jedes benutzerdefinierte Wort als Folge aufgelöster Operationen, damit spätere Neudefinitionen frühere Rümpfe nicht ändern.

Hinweis 3

Achte auf Details beim Parsen zur Definitionszeit: Worte nach ihrer aktuellen Bedeutung erfassen, Ausführung in Definitionen ignorieren und die Groß-/Kleinschreibung der Built-ins sowie abgeschnittene Division beachten.

Erwartete Komplexität

Zeit O(T), zusätzlicher Speicher O(T)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 1,390 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.