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] Chuyển biểu thức trung tố sang hậu tố

    Trong giai đoạn phân tích cú pháp của trình biên dịch, biểu thức trung tố (infix) thường được chuyển sang dạng hậu tố (postfix, Reverse Polish Notation) để thuận tiện cho việc sinh mã và định giá bằng máy ngăn xếp.

    Cho một biểu thức trung tố gồm các toán hạng là số nguyên không âm, các toán tử +,−,×,÷,^+, -, \times, \div, \hat{}+,−,×,÷,^ (ký hiệu lần lượt là + - * / ^) và dấu ngoặc đơn ( ). Hãy chuyển biểu thức về dạng hậu tố bằng thuật toán Shunting-yard (Dijkstra).

    Độ ưu tiên toán tử (từ thấp đến cao): +,−+,-+,− (kết hợp trái) < ×,÷<\ \times,\div< ×,÷ (kết hợp trái) < ^<\ \hat{}< ^ (kết hợp phải, lũy thừa).

    Ví dụ: với biểu thức 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3, kết quả hậu tố là 3 4 2 * 1 5 - 2 3 ^ ^ / +.

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

      Một dòng duy nhất chứa biểu thức trung tố, các token (số, toán tử, dấu ngoặc) cách nhau bởi đúng một khoảng trắng. Biểu thức luôn hợp lệ (ngoặc cân bằng, đúng cú pháp).

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

      In ra một dòng là biểu thức hậu tố tương ứng, các token cách nhau bởi đúng một khoảng trắng, không có khoảng trắng thừa ở đầu/cuối dòng.

    Ví dụ:

    Đầu vào:

    3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

    Đầu ra:

    3 4 2 * 1 5 - 2 3 ^ ^ / +

    Đầu vào:

    5

    Đầu ra:

    5

    Đang tải editor...