solution

Cho một biểu thức số học dạng trung tố chỉ gồm: biến (định danh chữ cái/số/_, bắt đầu bằng chữ cái hoặc _), hằng số nguyên không âm, các phép toán hai ngôi + - * / (không có phép trừ một ngôi), và cặp ngoặc đơn. Độ ưu tiên: ngoặc cao nhất; *, / (ngang hàng, kết hợp trái); thấp nhất +, - (ngang hàng, kết hợp trái).

Biểu diễn biểu thức dưới dạng cây nhị phân biểu thức (mỗi toán hạng là một lá, mỗi toán tử là một nút trong có đúng 2 con). Áp dụng thuật toán gán nhãn Sethi–Ullman để xác định số thanh ghi (biến tạm) tối thiểu đủ để sinh mã đánh giá biểu thức mà không cần lưu tạm ra bộ nhớ (spill), theo công thức đệ quy kinh điển: $\text{label(lá)} = 1$ $\text{label(nút)} = \begin{cases} \max(l_1, l_2) & \text{nếu } l_1 \ne l_2 \\ l_1 + 1 & \text{nếu } l_1 = l_2 \end{cases}$ trong đó $l_1, l_2$ là nhãn của hai cây con (thứ tự không quan trọng).

Ví dụ: với (a+b)+(c+d), cây con trái a+b có nhãn $2$ (hai lá cùng nhãn $1$), cây con phải c+d cũng có nhãn $2$; vì hai nhãn bằng nhau, nút gốc có nhãn $2+1=3$. Số nút trong (số lệnh TAC cần sinh) là $3$.