solution

Khi sinh mã bytecode cho một máy ảo dựa trên ngăn xếp (stack machine), trình biên dịch cần biết trước kích thước ngăn xếp toán hạng lớn nhất mà một đoạn mã có thể cần dùng, để cấp phát đúng vùng nhớ cho ngăn xếp đó (thay vì cấp phát động tốn kém). Đây là một phân tích tĩnh (static analysis) điển hình trên bytecode.

Cho một chương trình bytecode gồm các lệnh sau, thực thi tuần tự (không có lệnh nhảy):

• PUSH x: đẩy số nguyên $x$ vào đỉnh ngăn xếp.
• ADD, SUB, MUL, DIV: lấy ra hai phần tử trên đỉnh (gọi là $b$ rồi $a$ theo thứ tự lấy ra), tính $a+b$, $a-b$, $a \times b$ hoặc $a \div b$ (chia lấy phần nguyên, làm tròn về 0) rồi đẩy kết quả trở lại.
• DUP: nhân đôi phần tử trên đỉnh.
• POP: xoá phần tử trên đỉnh.
• SWAP: hoán đổi hai phần tử trên đỉnh.

Dữ liệu vào đảm bảo chương trình luôn hợp lệ: không bao giờ thiếu phần tử khi cần và không có phép chia cho 0.

Hãy tính: (1) kích thước ngăn xếp 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 (kể cả trạng thái ban đầu, kích thước $0$), (2) kích thước ngăn xếp sau khi thực thi xong toàn bộ chương trình, và (3) giá trị phần tử trên đỉnh ngăn xếp lúc kết thúc (nếu ngăn xếp rỗng lúc kết thúc, coi giá trị này là $0$).

Ví dụ: với chương trình PUSH 1, PUSH 2, PUSH 3, PUSH 4, ADD, ADD, ADD, ngăn xếp đạt kích thước lớn nhất là $4$ (sau 4 lệnh PUSH liên tiếp), kết thúc với kích thước $1$ và giá trị đỉnh là $10$.