Gộp hằng số (constant folding) là một phép tối ưu hoá phổ biến trên AST: trình biên dịch tìm các cây con mà mọi lá đều là hằng số (không chứa biến), tính trước giá trị của chúng, rồi thay cây con đó bằng một lá hằng số duy nhất — giúp giảm số phép tính phải thực hiện lúc chạy chương trình.
Cho một biểu thức tiền tố với toán tử hai ngôi +,−,×,÷, toán hạng là biến (một chữ cái thường) hoặc hằng số nguyên không âm. Hãy thực hiện gộp hằng số: với mỗi nút toán tử, nếu cả hai cây con đều là hằng số thuần túy (không chứa biến nào, xét đệ quy), thay nút đó bằng giá trị hằng số đã tính (dùng phép chia lấy phần nguyên làm tròn về 0 như C/C++, ví dụ −7÷2=−3). Các cây con còn chứa biến thì giữ nguyên cấu trúc, không áp dụng thêm bất kỳ luật đại số nào khác (ví dụ không rút gọn x×0 thành 0). Đề bảo đảm không xảy ra chia cho 0 trong bất kỳ cây con hằng số nào.
Một dòng duy nhất chứa các token của biểu thức tiền tố, cách nhau bởi khoảng trắng. Biểu thức luôn hợp lệ và không rỗng.
In ra một dòng là biểu thức tiền tố sau khi gộp hằng số, các token cách nhau bởi một khoảng trắng.
Ví dụ: với input + x * 2 3 (tức x+(2×3)), vì 2×3 là cây con toàn hằng số nên được gộp thành 6, output là + x 6. Với input + + a 2 3 (tức (a+2)+3), cây con a+2 chứa biến nên không gộp được toàn bộ, output giữ nguyên + + a 2 3.
Ví dụ:
Đầu vào:
+ 2 3
Đầu ra:
5
Đầu vào:
+ x * 2 3
Đầu ra:
+ x 6
Đang tải editor...