solution

Xét một máy ảo dựa trên ngăn xếp (stack machine) với tập lệnh:

• PUSH v: đẩy số nguyên $v$ vào đỉnh ngăn xếp;
• POP: bỏ phần tử ở đỉnh ngăn xếp;
• ADD, SUB, MUL: lấy hai phần tử ở đỉnh (gọi $a$ là phần tử đỉnh, $b$ là phần tử ngay dưới), tính $b+a$, $b-a$ hoặc $b \times a$ tương ứng rồi đẩy kết quả trở lại;
• DUP: nhân đôi phần tử ở đỉnh (đẩy thêm một bản sao của nó).

Đề bảo đảm ngăn xếp luôn đủ phần tử khi các lệnh trên được thực thi.

Một tối ưu peephole đơn giản: bất kỳ cặp lệnh liền kề PUSH v rồi ngay sau đó là POP đều không ảnh hưởng gì tới ngăn xếp (đẩy vào rồi lấy ra ngay), nên có thể loại bỏ cả cặp. Áp dụng việc loại bỏ này lặp lại: sau khi loại một cặp, hai lệnh mới trở nên liền kề có thể lại tạo thành một cặp PUSH v, POP mới và tiếp tục được loại bỏ, cho đến khi không còn cặp PUSH, POP liền kề nào (nói cách khác: đây là quá trình rút gọn giống với việc khử ngoặc khớp nhau bằng ngăn xếp, xét từ trái sang phải).

Yêu cầu:

1. In ra số lệnh còn lại sau khi tối ưu peephole.
2. Thực thi chương trình đã tối ưu (ngữ nghĩa được bảo toàn nên kết quả giống hệt chương trình gốc) và in ra toàn bộ ngăn xếp cuối cùng, liệt kê từ đáy lên đỉnh, cách nhau một khoảng trắng (in dòng trống nếu ngăn xếp rỗng).

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

PUSH 5
PUSH 3
POP
POP

cả 4 lệnh bị loại bỏ dần (POP thứ hai khử với PUSH 3, sau đó POP còn lại khử với PUSH 5), số lệnh còn lại là 0, ngăn xếp cuối rỗng.