Khi một trình biên dịch sinh mã máy ảo dựa trên ngăn xếp (stack machine) để tính giá trị một biểu thức hậu tố (Ba Lan ngược - Reverse Polish Notation), số lượng thanh ghi/ô nhớ ngăn xếp cần cấp phát phụ thuộc vào độ sâu lớn nhất mà ngăn xếp từng đạt tới trong quá trình tính.
Cho một biểu thức hậu tố hợp lệ gồm các toán hạng là chữ số đơn (từ 0 đến 9) và các toán tử hai ngôi + - * /. Quy tắc tính bằng ngăn xếp: gặp toán hạng thì đẩy (push) vào ngăn xếp; gặp toán tử thì lấy ra (pop) 2 phần tử trên đỉnh, tính kết quả rồi đẩy kết quả đó trở lại ngăn xếp.
Hãy xác định kích thước lớn nhất mà ngăn xếp từng đạt được trong toàn bộ quá trình xử lý biểu thức (không cần quan tâm giá trị số học thực sự, chỉ cần mô phỏng số phần tử trong ngăn xếp).
Ví dụ: với biểu thức hậu tố 1 2 + 3 4 + *, diễn biến kích thước ngăn xếp là: đẩy 1 (kích thước 1), đẩy 2 (2), + (1), đẩy 3 (2), đẩy 4 (3), + (2), * (1). Kích thước lớn nhất đạt được là 3.
Một dòng duy nhất chứa biểu thức hậu tố, các token (chữ số hoặc toán tử) cách nhau đúng một khoảng trắng. Biểu thức luôn hợp lệ (đủ toán hạng cho mọi toán tử).
In ra một số nguyên duy nhất là kích thước lớn nhất mà ngăn xếp từng đạt được.
Ví dụ:
Đầu vào:
5
Đầu ra:
1
Đầu vào:
3 4 +
Đầu ra:
2
Đang tải editor...