Đề bài
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.
Ràng buộc
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.
Ví dụ
Đầu vào:
program = ": square dup * ; 5 square 3 +"
Kết quả mong đợi:
expected = [28]Đầu vào:
std::string program = ": square dup * ; 5 square 3 +";
Kết quả mong đợi:
std::vector<long long> expected = {28};Đầu vào:
string program = ": square dup * ; 5 square 3 +";
Kết quả mong đợi:
long[] expected = new long[] {28};Giải thích
Define square without executing it. Push 5, duplicate it, multiply to get 25, then push 3 and add to obtain 28.
Đầu vào:
program = "-7 2 / 9 over"
Kết quả mong đợi:
expected = [-3, 9, -3]Đầu vào:
std::string program = "-7 2 / 9 over";
Kết quả mong đợi:
std::vector<long long> expected = {-3, 9, -3};Đầu vào:
string program = "-7 2 / 9 over";
Kết quả mong đợi:
long[] expected = new long[] {-3, 9, -3};Giải thích
−7 divided by 2 truncates toward zero to −3. Push 9, then OVER copies the second-from-top value, −3.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Hãy xem chương trình như hai việc đan xen: chạy stack hiện tại và nhớ ý nghĩa của từng word khi nó được định nghĩa.
Gợi ý 2
Lưu mỗi word do user định nghĩa thành một chuỗi operation đã được resolve, để redefinition sau này không đổi body cũ.
Gợi ý 3
Cẩn thận ở bước parse khi định nghĩa: bắt word theo nghĩa hiện tại, bỏ qua việc thực thi bên trong definition, và xử lý built-in không phân biệt hoa thường với phép chia làm tròn về 0.
Độ phức tạp mong đợi
thời gian O(T), bộ nhớ phụ O(T)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.