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] Trạng thái ngăn xếp cuối cùng của máy ảo

    Một máy ảo dựa trên ngăn xếp (stack-based virtual machine) thực thi chương trình bằng cách đọc lần lượt từng lệnh và thao tác trên một ngăn xếp (stack) chứa các số nguyên. Tập lệnh gồm:

    • PUSH x: đẩy số nguyên xxx vào đỉnh ngăn xếp.
    • ADD: lấy ra 2 phần tử trên cùng a,ba, ba,b (với bbb ở đỉnh, aaa ngay dưới bbb), đẩy lại a+ba+ba+b.
    • SUB: lấy ra a,ba, ba,b như trên, đẩy lại a−ba-ba−b.
    • MUL: lấy ra a,ba, ba,b như trên, đẩy lại a×ba \times ba×b.
    • DUP: nhân đôi phần tử ở đỉnh ngăn xếp (đẩy thêm một bản sao của giá trị đang ở đỉnh).
    • POP: bỏ (loại) phần tử ở đỉnh ngăn xếp.

    Cho một chương trình gồm nnn lệnh, đảm bảo mọi lệnh đều hợp lệ (không xảy ra tình huống lấy phần tử từ ngăn xếp rỗng). Hãy cho biết trạng thái ngăn xếp cuối cùng sau khi thực thi hết chương trình.

    Ví dụ: với chương trình

    PUSH 3
PUSH 4
ADD
PUSH 2
MUL

    ta có: [3]→[3,4]→[7]→[7,2]→[14][3] \to [3,4] \to [7] \to [7,2] \to [14][3]→[3,4]→[7]→[7,2]→[14]. Ngăn xếp cuối cùng là 14.

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

      Dòng đầu tiên chứa số nguyên nnn (0≤n≤10000 \le n \le 10000≤n≤1000) là số lệnh. nnn dòng tiếp theo, mỗi dòng là một lệnh theo đúng cú pháp nêu trên (riêng PUSH có thêm một số nguyên, các số nguyên trong chương trình và trong quá trình tính toán có trị tuyệt đối không vượt quá 10910^9109).

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

      In ra một dòng duy nhất là các phần tử của ngăn xếp cuối cùng, liệt kê từ đáy đến đỉnh, cách nhau bởi đúng một dấu cách. Nếu ngăn xếp rỗng, in ra một dòng trống.

    Ví dụ:

    Đầu vào:

    0

    Đầu ra:

    Đầu vào:

    5
PUSH 3
PUSH 4
ADD
PUSH 2
MUL

    Đầu ra:

    14

    Đang tải editor...