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] Số thanh ghi tối thiểu theo nhãn Sethi-Ullman

    Khi sinh mã máy cho một biểu thức số học từ mã ba địa chỉ, số thanh ghi tối thiểu cần thiết để tính biểu thức (không cần lưu tạm ra bộ nhớ) phụ thuộc vào thứ tự tính toán các nhánh con. Thuật toán gán nhãn Sethi–Ullman kinh điển xác định số này bằng đệ quy trên cây biểu thức:

    • Nút lá (toán hạng): nhãn =1= 1=1.
    • Nút toán tử hai ngôi với nhãn nhánh trái LLL, nhánh phải RRR:
      • nếu L=RL = RL=R: nhãn của nút =L+1= L+1=L+1;
      • nếu L≠RL \ne RL=R: nhãn của nút =max⁡(L,R)= \max(L,R)=max(L,R).

    Cho biểu thức dưới dạng dãy token hậu tố (postfix, như ở bài sinh TAC), hãy tính nhãn của nút gốc — chính là số thanh ghi tối thiểu cần dùng.

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

      Dòng 1: số nguyên nnn (1≤n≤1001 \le n \le 1001≤n≤100) — số token của biểu thức hậu tố. Dòng 2: nnn token cách nhau khoảng trắng, mỗi token là toán hạng (chữ thường a-z hoặc số nguyên không âm) hoặc toán tử trong + - * /. Dữ liệu đảm bảo là một biểu thức hậu tố hợp lệ.

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

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

    Ví dụ:

    Đầu vào:

    1
x

    Đầu ra:

    1

    Đầu vào:

    3
a b +

    Đầu ra:

    2

    Đang tải editor...