Khi sinh mã máy ảo ngăn xếp (ví dụ bytecode kiểu JVM), trình biên dịch cần xác định trước, tại thời điểm biên dịch, kích thước tối đa của ngăn xếp toán hạng (operand stack) mà đoạn mã sẽ cần, để cấp phát đúng bộ nhớ cho ngăn xếp đó khi thực thi — đại lượng này thường được gọi là max_stack.
Cho một đoạn mã máy ảo ngăn xếp gồm các lệnh PUSH x, ADD, SUB, MUL, DIV, POP, DUP, SWAP (ngữ nghĩa như các máy ảo ngăn xếp thông thường: PUSH tăng độ sâu ngăn xếp thêm 1; ADD, SUB, MUL, DIV, POP lấy ra các phần tử cần thiết và đẩy lại nhiều nhất 1 phần tử nên đều làm giảm độ sâu đi đúng 1; DUP tăng độ sâu thêm 1; SWAP không làm thay đổi độ sâu), hãy tính độ sâu ngăn xếp lớn nhất đạt được tại bất kỳ thời điểm nào trong quá trình xử lý tuần tự các lệnh, xuất phát từ ngăn xếp rỗng (độ sâu 0). Đây thuần túy là bài toán tính toán tĩnh (static analysis): bạn không cần và không được thực sự tính giá trị các phép toán số học.
Ví dụ: với PUSH 1 / PUSH 2 / PUSH 3 / ADD / ADD, độ sâu qua từng lệnh là 1,2,3,2,1, nên độ sâu tối đa là 3.
Dòng đầu tiên chứa số nguyên n (0≤n≤2000) — số lệnh. n dòng tiếp theo, mỗi dòng là một lệnh dạng PUSH x (x là số nguyên bất kỳ, giá trị cụ thể của x không ảnh hưởng tới kết quả) hoặc một trong các từ khóa ADD, SUB, MUL, DIV, POP, DUP, SWAP. Đề bảo đảm chương trình hợp lệ: không lệnh nào yêu cầu nhiều phần tử hơn số phần tử đang có trong ngăn xếp.
In ra đúng một số nguyên duy nhất — độ sâu ngăn xếp tối đa đạt được trong toàn bộ quá trình xử lý (nếu n=0, in ra 0).
Ví dụ:
Đầu vào:
5
PUSH 1
PUSH 2
PUSH 3
ADD
ADD
Đầu ra:
3
Đầu vào:
0
Đầu ra:
0
Đang tải editor...