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 dịch máy ngăn xếp tối giản

    Trong bước sinh mã của trình biên dịch, biểu thức thường được dịch sang mã cho một máy ngăn xếp (stack machine) rồi được thông dịch (interpret) trực tiếp. Ngăn xếp lưu các số nguyên (không giới hạn độ lớn, kiểu int của Python). Chương trình gồm các lệnh sau:

    • PUSH x: đẩy số nguyên xxx vào đỉnh ngăn xếp.
    • ADD, SUB, MUL: lấy bbb là phần tử đỉnh, aaa là phần tử ngay dưới bbb (pop cả hai), tính a+ba+ba+b, a−ba-ba−b, a×ba \times ba×b tương ứng rồi đẩy kết quả vào ngăn xếp.
    • DIV: lấy aaa (dưới), bbb (đỉnh). Nếu b=0b=0b=0: in ra dòng ERROR và dừng thực thi ngay (bỏ qua mọi lệnh còn lại). Ngược lại tính thương nguyên kiểu Python, tức ⌊a/b⌋\lfloor a/b \rfloor⌊a/b⌋ (toán tử //, làm tròn về −∞-\infty−∞), pop cả hai rồi đẩy kết quả.
    • DUP: nhân đôi phần tử đỉnh (đẩy thêm một bản sao của nó).
    • POP: bỏ phần tử đỉnh (không in gì).
    • PRINT: in ra giá trị hiện tại ở đỉnh ngăn xếp (không pop), trên một dòng riêng.

    Đảm bảo tại mọi thời điểm ngăn xếp có đủ phần tử cần thiết cho lệnh đang xét (trừ trường hợp chia cho 0 đã nêu ở trên).

    Ví dụ: với chương trình 4 lệnh PUSH 3, PUSH 4, ADD, PRINT thì kết quả in ra là một dòng duy nhất 7.

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

      Dòng đầu tiên là số nguyên nnn (0≤n≤10000 \le n \le 10000≤n≤1000) — số lệnh. nnn dòng tiếp theo, mỗi dòng là một lệnh theo đúng cú pháp trên (lệnh PUSH có thêm một số nguyên tham số, các lệnh khác không có tham số).

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

      In ra các dòng do lệnh PRINT sinh ra, theo đúng thứ tự thực thi. Nếu trong quá trình thực thi gặp DIV với số chia bằng 0, in thêm dòng ERROR ngay tại thời điểm đó rồi dừng (không in các PRINT sau đó nữa, kể cả khi lệnh đó lẽ ra được thực hiện).

    Ví dụ:

    Đầu vào:

    0

    Đầu ra:

    Đầu vào:

    4
PUSH 3
PUSH 4
ADD
PRINT

    Đầu ra:

    7

    Đang tải editor...