solution

Một trong những phép tối ưu hóa đơn giản nhất mà trình biên dịch thực hiện trên cây cú pháp AST là gộp hằng số (constant folding): nếu một nút toán tử có cả hai cây con đều là hằng số đã biết trước (không chứa biến), trình biên dịch sẽ tính luôn giá trị đó ở bước biên dịch, thay cả cây con bằng một nút lá hằng số duy nhất, thay vì để chương trình tính lại lúc chạy.

Cho một biểu thức tiền tố gồm các toán tử $\{+, -, *, /\}$, toán hạng là số nguyên (hằng số) hoặc chữ cái thường (biến). Hãy thực hiện gộp hằng số từ dưới lên trên toàn bộ cây: một cây con chỉ được gộp thành một hằng số nếu toàn bộ các lá của nó đều là hằng số; việc gộp thực hiện đệ quy nên một cây con lớn hơn vẫn có thể được gộp tiếp nếu sau khi gộp các cây con nhỏ, cả hai nhánh đều trở thành hằng số. Phép chia số nguyên được làm tròn về $0$ (giống C/C++), ví dụ $(-7)/2 = -3$. Đề bài đảm bảo không có phép chia cho 0 xảy ra trong suốt quá trình gộp.

Ví dụ: biểu thức - 10 * 2 3 — cây con * 2 3 gộp thành 6; sau đó nút gốc - có cả hai con là hằng số ($10$ và $6$) nên gộp tiếp thành 4. Kết quả cuối cùng là 4.