solution

Một trong những bài toán kinh điển của sinh mã tối ưu là xác định số thanh ghi tối thiểu cần thiết để đánh giá một biểu thức số học mà không cần lưu tạm (spill) bất kỳ giá trị trung gian nào ra bộ nhớ. Thuật toán Sethi–Ullman giải bài toán này bằng cách gán nhãn (label) cho từng nút của cây cú pháp biểu thức theo quy tắc quy nạp:

• Nhãn của một lá (biến hoặc hằng số) luôn bằng $1$.
• Xét nút trong có con trái $L$ và con phải $R$ với nhãn tương ứng là $\text{label}(L)$ và $\text{label}(R)$:
  • Nếu $\text{label}(L) \ne \text{label}(R)$ thì nhãn của nút bằng $\max(\text{label}(L), \text{label}(R))$.
  • Nếu $\text{label}(L) = \text{label}(R)$ thì nhãn của nút bằng $\text{label}(L) + 1$ (vì phải giữ kết quả của một bên trong thanh ghi trong lúc tính bên còn lại, cả hai bên cùng cần số thanh ghi như nhau).

Nhãn của gốc cây chính là số thanh ghi tối thiểu cần thiết. Cho một biểu thức viết dưới dạng tiền tố (prefix), gồm các token cách nhau bởi khoảng trắng: lá là một chữ cái thường (a-z) hoặc một số nguyên không âm; toán tử hai ngôi thuộc $\{+, -, *, /\}$ (mỗi toán tử luôn có đúng hai toán hạng ngay sau nó theo ngữ nghĩa tiền tố). Hãy tính nhãn Sethi–Ullman của gốc cây.

Ví dụ: biểu thức + a * b c (nghĩa là $a + b \times c$): lá a, b, c đều có nhãn 1; nút * b c có hai con cùng nhãn 1 nên nhãn là $1+1=2$; nút gốc + có con trái nhãn 1, con phải nhãn 2, khác nhau nên nhãn là $\max(1,2)=2$. Kết quả: 2.