Một trong những phép tối ưu mã cục bộ (peephole optimization) kinh điển là loại bỏ cặp lệnh PUSH/POP liền kề dư thừa trên một máy ảo ngăn xếp: đẩy một giá trị vào ngăn xếp rồi lập tức bỏ nó đi (không dùng vào việc gì) là vô nghĩa và có thể loại bỏ an toàn khỏi chương trình mà không làm thay đổi hành vi các lệnh còn lại.
Cho một danh sách lệnh (mỗi lệnh là PUSH x hoặc một trong các từ khoá ADD, SUB, MUL, DIV, DUP, POP, PRINT), hãy áp dụng thuật toán tối ưu sau (dùng một ngăn xếp phụ trợ S, ban đầu rỗng), duyệt các lệnh đầu vào lần lượt theo thứ tự xuất hiện:
POP và phần tử ở đỉnh S hiện tại là một lệnh dạng PUSH x (với x bất kỳ): loại bỏ phần tử đó khỏi đỉnh S (tức là cặp PUSH x — POP này bị triệt tiêu, không đưa lệnh POP vào S).Lưu ý việc triệt tiêu có thể tạo ra các cặp PUSH/POP liền kề mới (vì hai lệnh trước đó, vốn không liền kề, trở thành liền kề sau khi phần ở giữa bị loại) — thuật toán trên xử lý đúng việc này một cách tự nhiên nhờ dùng ngăn xếp phụ trợ.
Sau khi duyệt hết, nội dung của S (từ đáy lên đỉnh) chính là chương trình đã được tối ưu.
Ví dụ: với 4 lệnh PUSH 1, PUSH 2, POP, POP: PUSH 2 bị POP đầu tiên triệt tiêu, sau đó PUSH 1 bị POP thứ hai triệt tiêu — chương trình tối ưu rỗng (0 lệnh).
Dòng đầu tiên chứa số nguyên n (0≤n≤1000) — số lệnh.
n dòng tiếp theo, mỗi dòng một lệnh: PUSH x (−109≤x≤109) hoặc một trong ADD, SUB, MUL, DIV, DUP, POP, PRINT.
In ra dòng đầu tiên là số nguyên m — số lệnh còn lại sau khi tối ưu. m dòng tiếp theo là các lệnh còn lại, theo đúng thứ tự (giữ nguyên cú pháp gốc, ví dụ PUSH x giữ nguyên giá trị x).
Ví dụ:
Đầu vào:
0
Đầu ra:
0
Đầu vào:
2
PUSH 5
POP
Đầu ra:
0
Đang tải editor...