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] Thống kê mã máy ngăn xếp sinh từ hậu tố

    Một bộ sinh mã (code generator) đơn giản duyệt qua một biểu thức hậu tố (postfix) và với mỗi token sinh ra đúng một lệnh máy ngăn xếp: mỗi số hạng sinh ra một lệnh PUSH v; mỗi toán tử trong {+,−,∗,/}\{+, -, *, /\}{+,−,∗,/} sinh ra lệnh toán tử tương ứng (ADD, SUB, MUL, DIV), lệnh này pop hai phần tử — bbb ở đỉnh (mới hơn) và aaa ngay dưới — rồi đẩy lại a op ba \ \text{op} \ ba op b. Phép chia DIV lấy phần nguyên hướng về 0 (như (−7)÷2=−3(-7) \div 2 = -3(−7)÷2=−3); dữ liệu đảm bảo không chia cho 0 và biểu thức hợp lệ (đủ toán hạng cho mọi toán tử).

    Cho biểu thức hậu tố, hãy xác định 4 chỉ số của đoạn mã được sinh ra và của quá trình thực thi nó:

    1. Tổng số lệnh PUSH.
    2. Tổng số lệnh toán tử (ADD+SUB+MUL+DIV).
    3. Độ sâu ngăn xếp lớn nhất đạt được khi mô phỏng thực thi đoạn mã.
    4. Giá trị kết quả cuối cùng còn lại trên ngăn xếp.

    Ví dụ: với hậu tố 3 4 +, mã sinh ra là PUSH 3, PUSH 4, ADD — có 2 lệnh PUSH, 1 lệnh toán tử, độ sâu lớn nhất là 2 (khi ngăn xếp là [3,4][3,4][3,4]), kết quả cuối là 7. Kết quả in ra: 2 1 2 7.

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

      Một dòng duy nhất chứa biểu thức hậu tố hợp lệ: các token (số nguyên, có thể âm, hoặc một trong + - * /) cách nhau bởi khoảng trắng, tối đa 2000 token.

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

      In ra một dòng gồm 4 số nguyên cách nhau bởi khoảng trắng, theo đúng thứ tự: số lệnh PUSH, số lệnh toán tử, độ sâu ngăn xếp lớn nhất, giá trị kết quả cuối cùng.

    Ví dụ:

    Đầu vào:

    3 4 +

    Đầu ra:

    2 1 2 7

    Đầu vào:

    7

    Đầu ra:

    1 0 1 7

    Đang tải editor...