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] Bộ phân tích từ vựng và chuyển đổi hậu tố

    Khác với bài toán chuyển đổi trung tố sang hậu tố kinh điển (toán hạng một ký tự), trong một trình biên dịch thực sự, bước phân tích từ vựng (lexical analysis) phải tự tách chuỗi ký tự thô thành các token trước khi phân tích cú pháp.

    Cho một biểu thức trung tố (có thể không có khoảng trắng, hoặc có khoảng trắng tùy ý xen giữa các token), hãy:

    1. Tách token (tokenize) theo quy tắc maximal munch: định danh (identifier) là một chữ cái hoặc _ theo sau bởi các chữ cái/chữ số/_ (ví dụ x1, abc12, de3); số nguyên là một dãy chữ số liên tiếp (ví dụ 123); còn lại là các toán tử + - * / ^ và dấu ngoặc ( ).
    2. Chuyển sang hậu tố bằng giải thuật Shunting-Yard với độ ưu tiên: ^ cao nhất, kết hợp phải; *, / kế tiếp; +, - thấp nhất; các toán tử (trừ ^) kết hợp trái.

    Biểu thức đảm bảo hợp lệ, cân bằng ngoặc, không có dấu trừ một ngôi, và không có hai token loại định danh/số đứng dính liền nhau mà không có toán tử hay dấu ngoặc phân cách.

    Ví dụ: (x1+y2)*z3 →\to→ x1 y2 + z3 *.

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

      Một dòng (có thể chứa khoảng trắng ở bất kỳ vị trí nào, kể cả đầu/cuối dòng) chứa biểu thức trung tố gồm định danh, số nguyên không âm, các toán tử + - * / ^, dấu ngoặc ( ) và khoảng trắng tùy ý.

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

      In ra một dòng duy nhất là biểu thức hậu tố, các token cách nhau đúng một khoảng trắng.

    Ví dụ:

    Đầu vào:

    (x1+y2)*z3

    Đầu ra:

    x1 y2 + z3 *

    Đầu vào:

    abc+de*f

    Đầu ra:

    abc de f * +

    Đang tải editor...