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] Luật sinh lỗi: phục hồi biểu thức số học thiếu toán hạng/toán tử

    Luật sinh lỗi (error production) là kỹ thuật mở rộng văn phạm với các luật đặc biệt để nhận diện và "sửa" các lỗi cú pháp thường gặp ngay trong lúc phân tích. Xét biểu thức số học chỉ gồm số nguyên không âm và các toán tử + - * / (không có dấu ngoặc). Cho dãy nnn token, mỗi token hoặc là một số (chuỗi chữ số) hoặc là một trong bốn toán tử.

    Quét token từ trái sang phải, duy trì trạng thái đang mong đợi (expect) bắt đầu là mong đợi số (N), theo luật sau:

    • Đang mong đợi N mà gặp số: chấp nhận, chuyển sang mong đợi toán tử (O).
    • Đang mong đợi N mà gặp toán tử: đây là lỗi thiếu toán hạng; áp dụng luật sinh lỗi bằng cách chèn một số ảo 0 ngay trước toán tử đó, rồi chấp nhận toán tử, chuyển sang mong đợi N.
    • Đang mong đợi O mà gặp toán tử: chấp nhận, chuyển sang mong đợi N.
    • Đang mong đợi O mà gặp số: đây là lỗi thiếu toán tử; chèn toán tử ảo + ngay trước số đó, rồi chấp nhận số, chuyển sang mong đợi O.
    • Sau khi quét hết dãy, nếu trạng thái đang là mong đợi N (biểu thức kết thúc bằng toán tử hoặc rỗng): đây là lỗi thiếu toán hạng ở cuối biểu thức; chèn thêm số ảo 0 vào cuối.

    Sau khi thu được biểu thức đã phục hồi (luôn có dạng số, toán tử, số, ..., số hợp lệ), tính giá trị của biểu thức theo đúng thứ tự ưu tiên toán học chuẩn (*, / trước, +, - sau, kết hợp trái). Nếu trong lúc tính có phép chia cho 0 (do số bị chia là 0, kể cả số 0 được chèn ảo) thì không tính được kết quả.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên nnn (0≤n≤5000 \le n \le 5000≤n≤500) — số token.
      • Dòng 2: nnn token cách nhau bởi khoảng trắng, mỗi token là một số nguyên không âm (không quá 6 chữ số) hoặc một trong + - * / (rỗng nếu n=0n = 0n=0).
    • Định dạng đầu ra:

      In các lỗi theo đúng thứ tự phát hiện, mỗi lỗi một dòng dạng Vi tri {p}: {mô tả lỗi} với đúng ba dạng mô tả sau: thieu toan hang, da chen '0', thieu toan tu, da chen '+', hoặc thieu toan hang o cuoi bieu thuc, da chen '0' (vị trí ppp của lỗi cuối biểu thức là n+1n+1n+1). Sau đó in: Tong so loi: {tổng số lỗi}. Rồi in: Bieu thuc da phuc hoi: {biểu thức sau phục hồi, các token cách nhau một khoảng trắng}. Cuối cùng in kết quả: nếu tính được, Ket qua: {giá trị} với giá trị được làm tròn và hiển thị đúng 4 chữ số thập phân; nếu có chia cho 0, in Ket qua: khong xac dinh (chia cho 0).

    Ví dụ:

    Đầu vào:

    4
3 + * 4

    Đầu ra:

    Vi tri 3: thieu toan hang, da chen '0'
Tong so loi: 1
Bieu thuc da phuc hoi: 3 + 0 * 4
Ket qua: 3.0000

    Đầu vào:

    5
3 + 4 * 2

    Đầu ra:

    Tong so loi: 0
Bieu thuc da phuc hoi: 3 + 4 * 2
Ket qua: 11.0000

    Đang tải editor...