solution

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

Biểu thức đầu vào được cho dưới dạng cây, biểu diễn theo cú pháp tiền tố có ngoặc (S-expression), với văn phạm:

$E ::= \text{number} \mid \text{variable} \mid ( \ op \ E \ E \ )$

trong đó op $\in \{+, -, *\}$, number là số nguyên (có thể âm), variable là chuỗi chữ cái thường (không phải là số). Trong chuỗi đầu vào, mỗi dấu ngoặc, toán tử, số, biến đều là một token riêng biệt, các token cách nhau đúng một khoảng trắng — ví dụ ( + ( * 2 3 ) x ).

Hãy tối ưu hoá cây bằng cách gấp hằng số một cách đệ quy, từ lá lên gốc: với mỗi nút toán tử, nếu sau khi đã tối ưu đệ quy cả hai cây con, cả hai đều là hằng số, thay nút đó bằng hằng số kết quả của phép toán; ngược lại (có ít nhất một cây con còn chứa biến) giữ nguyên cấu trúc ( op E E ) với hai cây con đã được tối ưu. Đề bài không yêu cầu áp dụng thêm quy tắc đại số nào khác (như $x+0=x$).

Ví dụ: ( + ( * 2 3 ) x ) $\to$ ( + 6 x ) (vì ( * 2 3 ) gấp được thành $6$, còn $x$ là biến nên toàn bộ phép + không gấp được nữa).