solution

Khác với chế độ hoảng loạn (chỉ bỏ qua phần tử lỗi), nhiều trình soạn thảo/biên dịch dùng chiến lược phục hồi bằng chèn thêm ký hiệu để tự động "vá" lỗi ngoặc lệch. Cho chuỗi $s$ chỉ chứa 3 loại ngoặc ()[]{} và có thể xen lẫn ký tự khác (giữ nguyên, không ảnh hưởng thuật toán), hãy mô phỏng thuật toán sửa lỗi sau, dùng ngăn xếp:

Duyệt $s$ từ trái sang phải, xây dựng dần chuỗi kết quả:

• Ký tự mở: đẩy vào ngăn xếp, thêm vào kết quả.
• Ký tự khác (không phải ngoặc): thêm nguyên vẹn vào kết quả, không đổi ngăn xếp.
• Ký tự đóng $c$: lặp lại quy trình sau cho đến khi dừng (dừng khi ngăn xếp rỗng, hoặc $c$ khớp với đỉnh ngăn xếp):
  • Nếu ngăn xếp rỗng: $c$ là "thừa" (spurious) — loại bỏ $c$ (không thêm vào kết quả), tăng biến đếm discards, dừng vòng lặp cho ký tự này.
  • Ngược lại, gọi $e$ là ký tự đóng tương ứng với đỉnh ngăn xếp. Nếu $c = e$: khớp, lấy đỉnh ra khỏi ngăn xếp, thêm $c$ vào kết quả, dừng vòng lặp cho ký tự này. Nếu $c \ne e$: giả định ngoặc ở đỉnh đang bị thiếu ký tự đóng $e$ — chèn $e$ vào kết quả, tăng biến đếm insertions, lấy đỉnh ra khỏi ngăn xếp, rồi lặp lại (so sánh tiếp $c$ với đỉnh mới của ngăn xếp).

Sau khi duyệt hết $s$, nếu ngăn xếp còn ký tự mở dư, lần lượt lấy ra từng ký tự (từ đỉnh xuống đáy) và chèn ký tự đóng tương ứng vào cuối kết quả (mỗi lần tăng insertions).

In ra 2 số insertions discards, và chuỗi kết quả sau khi sửa.

Ví dụ: $s=$ (a[b)c]. Xử lý: ( đẩy, a giữ nguyên, [ đẩy, b giữ nguyên; gặp ): đỉnh là [ cần đóng bằng ] $\ne$ ) $\Rightarrow$ chèn ], lấy [ ra (insertions=1); so lại ) với đỉnh mới ( cần đóng bằng ) $=$ ) $\Rightarrow$ khớp, lấy ( ra, thêm ); c giữ nguyên; gặp ]: ngăn xếp rỗng $\Rightarrow$ thừa, loại bỏ (discards=1). Kết quả: insertions=1, discards=1, chuỗi sửa: (a[b])c.