solution

Xét văn phạm mô tả một danh sách lồng nhau, với $\text{ID}$ là một định danh gồm một hoặc nhiều chữ cái thường (a-z):

$S \to [ \; L \; ] \mid \text{ID}$ $L \to S \; ( \, , \, S \, )^{*}$

Dữ liệu vào luôn đảm bảo hợp lệ theo văn phạm trên (không có khoảng trắng, không có lỗi cú pháp), vì vậy không cần xử lý lỗi.

Hãy cài đặt một bộ phân tích cú pháp đệ quy gồm hai hàm tương ứng parse_S, parse_L; mỗi khi hàm parse_S được gọi với một tham số depth (độ sâu lồng ngoặc hiện tại bao quanh, ID ở mức ngoài cùng không nằm trong ngoặc nào có depth = 0), hãy:

1. Tính độ sâu lồng lớn nhất xuất hiện trong toàn chuỗi: mỗi cặp ngoặc vuông [...] làm tăng độ sâu của các thành phần bên trong nó thêm 1 so với độ sâu của chính nó.
2. Đếm tổng số định danh (lá) xuất hiện trong toàn chuỗi (đếm cả các định danh trùng tên).

Ví dụ: với chuỗi [a,[b,c],[[d]]]: a ở độ sâu 1; [b,c] làm b, c ở độ sâu 2; [[d]] làm d ở độ sâu 3. Độ sâu lớn nhất là 3, tổng số định danh là 4 (a, b, c, d).