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] Sinh mã máy ảo ngăn xếp từ biểu thức hậu tố

    Trong giai đoạn sinh mã (code generation) của trình biên dịch, một biểu thức đã được chuyển sang dạng hậu tố (postfix / Reverse Polish Notation) thường được dịch trực tiếp thành một dãy lệnh cho máy ảo ngăn xếp (stack machine): mỗi toán hạng sinh ra một lệnh đẩy giá trị vào ngăn xếp, mỗi toán tử sinh ra một lệnh thực hiện phép toán trên đỉnh ngăn xếp.

    Cho một biểu thức hậu tố, hãy sinh ra dãy lệnh mã máy ảo ngăn xếp tương ứng theo đúng thứ tự các token xuất hiện trong biểu thức (đây là bài toán sinh mã — bạn không cần và không được tính giá trị của biểu thức).

    Quy tắc dịch từng token sang lệnh:

    • Toán hạng là số nguyên xxx (có thể âm) ⇒\Rightarrow⇒ lệnh PUSH x.
    • Toán tử + ⇒\Rightarrow⇒ lệnh ADD.
    • Toán tử - ⇒\Rightarrow⇒ lệnh SUB.
    • Toán tử * ⇒\Rightarrow⇒ lệnh MUL.
    • Toán tử / ⇒\Rightarrow⇒ lệnh DIV.

    Ví dụ: với biểu thức hậu tố 3 4 +, mã sinh ra là:

    PUSH 3
PUSH 4
ADD
    • Định dạng đầu vào:

      Một dòng duy nhất chứa biểu thức hậu tố, các token (số nguyên hoặc toán tử) cách nhau bởi đúng một khoảng trắng. Toán hạng là số nguyên (có thể có dấu - ở đầu để biểu diễn số âm, ví dụ -3); toán tử là một trong bốn ký tự + - * / đứng riêng một mình (không dính với số). Đề bảo đảm biểu thức hậu tố hợp lệ về mặt cú pháp (số toán hạng luôn đủ cho mọi toán tử) và không rỗng.

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

      In ra các lệnh máy ảo ngăn xếp, mỗi lệnh một dòng, theo đúng thứ tự các token trong biểu thức đầu vào. Lệnh PUSH x in kèm giá trị x (không có số 0 thừa ở đầu), các lệnh ADD, SUB, MUL, DIV in đúng như tên (chữ in hoa, không kèm tham số).

    Ví dụ:

    Đầu vào:

    5

    Đầu ra:

    PUSH 5

    Đầu vào:

    3 4 +

    Đầu ra:

    PUSH 3
PUSH 4
ADD

    Đang tải editor...