solution

Rút gọn hằng số (constant folding) là một phép tối ưu hoá phổ biến được thực hiện trên AST trong trình biên dịch: mọi cây con mà giá trị của nó có thể tính được ngay tại thời điểm biên dịch (chỉ chứa hằng số) sẽ được thay bằng một nút lá chứa kết quả.

Cho một biểu thức trung tố gồm số nguyên không âm (hằng số), biến (một chữ cái thường), các toán tử + - * / và dấu ngoặc (không có ^, không có toán tử một ngôi; độ ưu tiên chuẩn, * / trước + -, kết hợp trái). Hãy dựng AST, sau đó rút gọn hằng số theo quy tắc: xét từng nút toán tử theo thứ tự từ dưới lên (hậu tố); nếu cả hai cây con của nút (sau khi đã rút gọn) đều là hằng số, thay nút đó bằng hằng số kết quả - riêng với phép /, chỉ rút gọn khi phép chia hết đúng (dư $0$) và mẫu khác $0$; nếu không thoả (chia không hết) thì giữ nguyên nút toán tử đó (không rút gọn), dù hai con đều là hằng số.

In ra AST sau khi rút gọn dưới dạng tiền tố đầy đủ ngoặc (như bài dựng AST từ trung tố): lá là hằng số in ra dạng số nguyên thập phân (có thể âm, ví dụ -7), lá là biến in ra tên biến; nút toán tử in dạng (op left right).

Ví dụ: x+2*3 - cây con 2*3 rút gọn thành 6, còn x không rút gọn được, kết quả là (+ x 6). Biểu thức 10/3+x: 10/3 không chia hết nên giữ nguyên, kết quả là (+ (/ 10 3) x).