solution

Trong giai đoạn phân tích cú pháp, khi bộ phân tích gặp lỗi, một chiến lược phục hồi đơn giản là chế độ hoảng loạn (panic mode): thay vì dừng chương trình ngay khi gặp lỗi đầu tiên, bộ phân tích bỏ qua phần tử gây lỗi và tiếp tục xử lý phần còn lại, đồng thời tăng biến đếm lỗi.

Cho một chuỗi $s$ (có thể rỗng) gồm các ký tự tuỳ ý, trong đó ta chỉ quan tâm đến 3 loại dấu ngoặc: ( ), [ ], { }. Mọi ký tự khác được bỏ qua hoàn toàn (không ảnh hưởng đến việc kiểm tra).

Bộ kiểm tra dùng một ngăn xếp (stack), duyệt qua $s$ từ trái sang phải:

• Gặp ký tự mở ((, [, {): đẩy vào ngăn xếp.
• Gặp ký tự đóng (), ], }):
  • Nếu ngăn xếp không rỗng và đỉnh ngăn xếp là ký tự mở tương ứng: lấy đỉnh ra khỏi ngăn xếp (khớp thành công).
  • Ngược lại (ngăn xếp rỗng, hoặc đỉnh không tương ứng): đây là 1 lỗi. Áp dụng panic mode: bỏ qua ký tự đóng gây lỗi này (không thay đổi ngăn xếp) và tiếp tục với ký tự kế tiếp của $s$.

Sau khi duyệt hết $s$, nếu ngăn xếp còn dư các ký tự mở chưa được đóng, mỗi ký tự mở còn dư cũng tính là 1 lỗi.

Yêu cầu: in ra tổng số lỗi phát hiện được.

Ví dụ: với $s =$ (a[b)c], quá trình xử lý: ( đẩy vào ngăn xếp; a bỏ qua; [ đẩy vào ngăn xếp; b bỏ qua; ) không khớp với đỉnh [ $\Rightarrow$ 1 lỗi, bỏ qua ); c bỏ qua; ] khớp với đỉnh [, lấy ra; kết thúc, ngăn xếp còn dư ( $\Rightarrow$ thêm 1 lỗi. Tổng cộng: $2$ lỗi.