solution

Một máy ảo ngăn xếp (stack machine) là mô hình thực thi trung gian phổ biến mà trình biên dịch sinh mã (code generation) hướng tới: mỗi biểu thức được dịch thành một dãy lệnh thao tác trên một ngăn xếp (stack) các số nguyên.

Cho một chương trình gồm $n$ lệnh, mỗi lệnh thuộc một trong các dạng sau:

• PUSH x: đẩy số nguyên $x$ (có thể âm) vào đỉnh ngăn xếp.
• ADD, SUB, MUL, DIV: lấy ra hai phần tử trên cùng ngăn xếp — gọi $b$ là phần tử ở đỉnh (vừa đẩy vào sau) và $a$ là phần tử ngay dưới nó (đẩy vào trước) — tính $a \ \text{op} \ b$ rồi đẩy kết quả trở lại ngăn xếp. Với DIV, phép chia lấy phần nguyên theo hướng làm tròn về 0 (như toán tử chia nguyên trong C/C++, ví dụ $(-7) \div 2 = -3$); dữ liệu vào đảm bảo không có phép chia cho 0.

Chương trình đảm bảo tại mọi thời điểm, khi thực hiện ADD/SUB/MUL/DIV thì ngăn xếp có ít nhất 2 phần tử, và khi kết thúc chương trình, ngăn xếp không rỗng.

Hãy mô phỏng việc thực thi và cho biết: (1) giá trị ở đỉnh ngăn xếp sau khi thực hiện xong toàn bộ $n$ lệnh, và (2) độ sâu ngăn xếp (số phần tử) lớn nhất từng đạt được tại bất kỳ thời điểm nào trong quá trình thực thi — đây chính là chỉ số mà trình biên dịch dùng để ước lượng dung lượng ngăn xếp cần cấp phát cho hàm.

Ví dụ: với chương trình gồm 5 lệnh PUSH 3, PUSH 4, ADD, PUSH 2, MUL, ngăn xếp diễn biến $[3] \to [3,4] \to [7] \to [7,2] \to [14]$. Độ sâu lớn nhất là 2 (đạt được khi ngăn xếp là $[3,4]$ hoặc $[7,2]$), giá trị cuối cùng là 14. Kết quả: 14 2.