Bài tập | NEU OJ

Trình biên dịch khi sinh mã bytecode cho máy ảo ngăn xếp cần biết trước kích thước ngăn xếp tối đa mà một hàm cần dùng, để cấp phát đúng vùng nhớ cho khung ngăn xếp (stack frame). Cho một đoạn chương trình bytecode thẳng (không có lệnh nhảy/rẽ nhánh), gồm các lệnh:

PUSH x: đẩy 1 phần tử vào ngăn xếp (kích thước ngăn xếp tăng 1).
ADD, SUB, MUL, DIV: lấy ra 2 phần tử ở đỉnh, đẩy vào 1 kết quả (kích thước ngăn xếp giảm 1). Lệnh này yêu cầu ngăn xếp phải có ít nhất 2 phần tử tại thời điểm thực hiện.
DUP: nhân đôi phần tử ở đỉnh ngăn xếp (kích thước tăng 1). Yêu cầu ngăn xếp có ít nhất 1 phần tử.
POP: bỏ phần tử ở đỉnh ngăn xếp (kích thước giảm 1). Yêu cầu ngăn xếp có ít nhất 1 phần tử.

Ngăn xếp ban đầu rỗng (kích thước 0). Hãy mô phỏng chương trình theo đúng thứ tự các dòng lệnh. Nếu tại một lệnh nào đó, ngăn xếp không đủ phần tử để thực hiện yêu cầu (thiếu hụt — underflow), hãy báo lỗi tại lệnh đó và dừng ngay, không xét các lệnh tiếp theo. Nếu không có lỗi nào xảy ra trong suốt chương trình, hãy cho biết kích thước ngăn xếp lớn nhất từng đạt được (tính cả trạng thái ban đầu bằng 0) và kích thước ngăn xếp cuối cùng sau khi thực hiện lệnh cuối.

Ví dụ: chương trình PUSH 1 / PUSH 2 / ADD / DUP có kích thước ngăn xếp lần lượt là $1, 2, 1, 2$ — không có lỗi, kích thước tối đa là $2$ , kích thước cuối cùng là $2$ .

Định dạng đầu vào:
Dòng đầu tiên chứa số nguyên $n$ ( $1 \le n \le 1000$ ). $n$ dòng tiếp theo, mỗi dòng là một trong các lệnh PUSH x, ADD, SUB, MUL, DIV, DUP, POP (chương trình không chứa PRINT, HALT hay lệnh nhảy).
Định dạng đầu ra:
Nếu xảy ra thiếu hụt ngăn xếp tại dòng lệnh thứ $k$ (đánh số từ 1, tính theo thứ tự trong $n$ dòng lệnh — không tính dòng đầu chứa $n$ ), in ra đúng một dòng theo định dạng:
```
UNDERFLOW k
```
Ngược lại (không có lỗi), in ra một dòng gồm hai số nguyên cách nhau một khoảng trắng: kích thước ngăn xếp tối đa và kích thước ngăn xếp cuối cùng.

solution

Đề bài: [Trình biên dịch] Độ sâu ngăn xếp cực đại của bytecode