Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Đánh số Sethi–Ullman trên AST

    Trong giai đoạn sinh mã của trình biên dịch, thuật toán đánh số Sethi-Ullman trên AST của biểu thức số học cho biết số thanh ghi tối thiểu cần dùng để tính biểu thức mà không cần lưu tạm ra bộ nhớ (không tràn thanh ghi), giả sử có đủ thanh ghi và mỗi toán tử là nhị phân.

    Nhãn Sethi-Ullman L(n)L(n)L(n) của một nút nnn được định nghĩa đệ quy như sau:

    • Nếu nnn là lá (toán hạng): L(n)=1L(n) = 1L(n)=1.
    • Nếu nnn là nút toán tử với hai con l,rl, rl,r: L(n)={L(l)+1neˆˊu L(l)=L(r)max⁡(L(l),L(r))neˆˊu L(l)≠L(r)L(n) = \begin{cases} L(l) + 1 & \text{nếu } L(l) = L(r) \\ \max(L(l), L(r)) & \text{nếu } L(l) \ne L(r) \end{cases}L(n)={L(l)+1max(L(l),L(r))​neˆˊu L(l)=L(r)neˆˊu L(l)=L(r)​

    Cho AST dưới dạng biểu thức tiền tố (toán tử hai ngôi thuộc + - * /, toán hạng là số nguyên không âm hoặc biến - nội dung toán hạng không ảnh hưởng tới kết quả, chỉ hình dạng cây mới quan trọng). Hãy tính L(goˆˊc)L(\text{gốc})L(goˆˊc).

    Ví dụ: + + a b + c d có hai cây con của gốc đều là + x y (mỗi bên có nhãn 1+1=21+1=21+1=2 vì hai lá bằng nhau); hai nhãn con bằng nhau nên nhãn gốc là 2+1=32+1=32+1=3.

    • Định dạng đầu vào:

      Một dòng duy nhất gồm các token cách nhau bởi một dấu cách: toán tử + - * / hoặc toán hạng (số nguyên không âm hoặc một chữ cái thường). Dãy token tạo thành đúng một AST nhị phân hợp lệ.

    • Định dạng đầu ra:

      In ra một số nguyên duy nhất - nhãn Sethi-Ullman của gốc AST (số thanh ghi tối thiểu cần thiết).

    Ví dụ:

    Đầu vào:

    x

    Đầu ra:

    1

    Đầu vào:

    + a b

    Đầu ra:

    2

    Đang tải editor...