solution

Xét văn phạm phi ngữ cảnh sinh biểu thức số học không chứa khoảng trắng, chỉ gồm chữ số $0$-$9$ (mỗi số là một chữ số), các phép toán $+, -, *, /$ và dấu ngoặc đơn:

$E \to T\ \big((+|-)\ T\big)^*$ $T \to F\ \big((*|/)\ F\big)^*$ $F \to d \ \mid\ ( \ E \ )$

trong đó $d$ là một chữ số từ $0$ đến $9$.

Cho một chuỗi $s$ được sinh đúng theo văn phạm $E$ ở trên (đảm bảo hợp lệ cú pháp, dấu ngoặc cân bằng). Hãy cài đặt một bộ phân tích cú pháp đệ quy xuống (recursive descent) gồm ba hàm tương ứng ba ký hiệu $E, T, F$, đồng thời theo dõi độ sâu lồng ngoặc trong quá trình phân tích: mỗi lần hàm $F$ gặp ngoặc mở và gọi đệ quy vào $E$ bên trong, độ sâu tăng thêm $1$ so với lời gọi hiện tại. Độ sâu của biểu thức ở mức ngoài cùng (không nằm trong ngoặc nào) là $0$.

Yêu cầu: in ra độ sâu lồng ngoặc lớn nhất đạt được trong toàn bộ quá trình phân tích.

Ví dụ: với $s =$ 1+(2*(3-4)), ngoặc ngoài có độ sâu $1$, ngoặc trong (chứa 3-4) có độ sâu $2$ → kết quả là $2$.