solution

Gấp hằng số (constant folding) là một phép tối ưu hoá kinh điển trong trình biên dịch: tại thời điểm biên dịch, nếu một phép toán có cả hai toán hạng đều là hằng số đã biết, trình biên dịch tính luôn kết quả và thay thế toàn bộ phép toán đó bằng một hằng số duy nhất, giúp giảm số lệnh phải sinh ra lúc chạy chương trình.

Cho một biểu thức hậu tố mà toán hạng là số nguyên (hằng số, có thể âm, không có dấu cách bên trong một token số) hoặc biến (một chữ cái thường a-z), toán tử hai ngôi thuộc $\{+,-,\times\}$ (viết + - *; đề này không có phép chia để tránh trường hợp không chia hết). Hãy dựng cây cú pháp của biểu thức rồi thực hiện gấp hằng số theo quy tắc: xét từng nút toán tử từ dưới lên (bottom-up); nếu cả hai cây con của nút đó đều đã là hằng số (có thể là do đã được gấp từ bước trước) thì thay nút đó bằng hằng số kết quả; nếu có ít nhất một cây con là biến (hoặc là một nút toán tử không gấp được) thì giữ nguyên nút toán tử đó.

In ra biểu thức hậu tố của cây kết quả sau khi gấp hằng số (duyệt postorder), và số toán tử đã bị loại bỏ nhờ gấp hằng số (bằng số toán tử của biểu thức gốc trừ số toán tử còn lại của biểu thức sau khi gấp).

Ví dụ: hậu tố a 2 3 + * — hai hằng số $2,3$ được gấp thành $5$, còn phép nhân với biến $a$ không gấp được, kết quả là a 5 *, số toán tử bị loại là $1$.