Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Định vị lỗi ngoặc đầu tiên

    Một chiến lược xử lý lỗi cú pháp phổ biến của trình biên dịch là chỉ báo cáo lỗi đầu tiên rồi dừng phân tích phần còn lại của mã nguồn, nhằm tránh hiện tượng "lỗi dây chuyền" (cascading errors) — một lỗi gốc sinh ra hàng loạt lỗi giả về sau.

    Xét bài toán kiểm tra cân bằng ngoặc trong mã nguồn, với ba loại ngoặc: ( ), [ ], { }. Mã nguồn gồm nhiều dòng; mọi ký tự khác ngoặc đều bị bỏ qua.

    Duyệt các ký tự theo đúng thứ tự xuất hiện: từ dòng 1 đến dòng cuối, trong mỗi dòng từ trái sang phải. Dùng một ngăn xếp để theo dõi các dấu mở chưa đóng:

    • Gặp dấu mở ((, [, {): đẩy vào ngăn xếp cùng vị trí (dòng, cột) của nó.
    • Gặp dấu đóng:
      • Nếu ngăn xếp đang rỗng: đây là lỗi "thừa dấu đóng".
      • Nếu đỉnh ngăn xếp là một dấu mở không cùng loại (ví dụ đỉnh là [ nhưng gặp )): đây là lỗi "dấu đóng không khớp".
      • Nếu khớp loại: lấy phần tử đó ra khỏi ngăn xếp (coi như cặp đã đóng đúng).

    Ngay khi phát hiện lỗi đầu tiên theo thứ tự duyệt, in ra lỗi đó và dừng (không xét tiếp phần còn lại).

    Nếu duyệt hết mã nguồn mà không gặp lỗi thừa/không khớp, nhưng ngăn xếp vẫn còn phần tử (có dấu mở chưa được đóng), đó là lỗi "thiếu dấu đóng", và vị trí báo cáo là vị trí của dấu mở được đẩy vào ngăn xếp sớm nhất còn sót lại (phần tử ở đáy ngăn xếp).

    Nếu ngăn xếp rỗng và không có lỗi nào ở trên, mã nguồn hợp lệ.

    Ví dụ: mã nguồn 2 dòng

    a(b[c)d]
e)

    Duyệt dòng 1: a (cột 1, bỏ qua), ( (cột 2, đẩy), b (cột 3), [ (cột 4, đẩy), c (cột 5), ) (cột 6) — đỉnh ngăn xếp hiện là [ (mở ở cột 4), nhưng gặp ) không khớp loại ([ cần đóng bằng ]). Đây là lỗi đầu tiên, in ra ngay và dừng, không xét tiếp d, ] hay dòng 2.

    • Định dạng đầu vào:

      Dòng đầu tiên chứa số nguyên nnn (0≤n≤10000 \le n \le 10000≤n≤1000) — số dòng mã nguồn. nnn dòng tiếp theo là nội dung từng dòng (có thể rỗng, có thể chứa bất kỳ ký tự nào; độ dài mỗi dòng không quá 200).

    • Định dạng đầu ra:

      In ra đúng một dòng:

      • Nếu không có lỗi: in OK.
      • Nếu có lỗi thừa dấu đóng tại dòng LLL cột CCC (1-based) với ký tự ch: in Line L Col C: unexpected closing 'ch'.
      • Nếu có lỗi không khớp tại dòng LLL cột CCC với ký tự đóng gặp phải ch và ký tự đóng được kỳ vọng ch2 (tương ứng dấu mở ở đỉnh ngăn xếp): in Line L Col C: mismatched closing 'ch', expected 'ch2'.
      • Nếu thiếu dấu đóng cho dấu mở och tại dòng LLL cột CCC (vị trí của chính dấu mở đó): in Line L Col C: missing closing for 'och'.

      Với ví dụ trong đề, kết quả in ra là: Line 1 Col 6: mismatched closing ')', expected ']'.

    Ví dụ:

    Đầu vào:

    3
foo(a, [b,c])
  x = {1,2}
y

    Đầu ra:

    OK

    Đầu vào:

    2
a(b[c)d]
e)

    Đầu ra:

    Line 1 Col 6: mismatched closing ')', expected ']'

    Đang tải editor...