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] Đếm số lần gọi hàm trong bộ phân tích cú pháp đệ quy

    Xét văn phạm biểu thức số học (không có dấu trừ một ngôi):

    E→T  ((+∣−)  T)∗T→F  ((×∣/)  F)∗F→NUM∣( E )E \to T \; \big( (+ \mid -) \; T \big)^{*} \qquad T \to F \; \big( (\times \mid /) \; F \big)^{*} \qquad F \to \text{NUM} \mid ( \, E \, )E→T((+∣−)T)∗T→F((×∣/)F)∗F→NUM∣(E)

    và một cài đặt bộ phân tích cú pháp đệ quy chuẩn tắc dùng ba hàm parse_E, parse_T, parse_F theo giả mã sau (mỗi hàm tăng bộ đếm của chính nó thêm 1 ngay khi vừa được gọi, trước khi làm bất cứ việc gì khác):

    parse_E():
    count_E += 1
    parse_T()
    while ky_tu_tiep_theo in {'+', '-'}:
        tieu_thu('+' hoac '-'); parse_T()

parse_T():
    count_T += 1
    parse_F()
    while ky_tu_tiep_theo in {'*', '/'}:
        tieu_thu('*' hoac '/'); parse_F()

parse_F():
    count_F += 1
    neu ky_tu_tiep_theo la SO:
        tieu_thu(SO)
    nguoc_lai (ky_tu_tiep_theo la '('):
        tieu_thu('('); parse_E(); tieu_thu(')')

    Với lệnh gọi ban đầu parse_E() trên một biểu thức đầu vào hợp lệ (không có khoảng trắng), hãy tính tổng số lần mỗi hàm được gọi (tính cả các lệnh gọi đệ quy lồng nhau) trong suốt quá trình phân tích.

    Ví dụ: với 3+4*2: parse_E được gọi 1 lần (ở ngoài cùng); parse_T được gọi 2 lần (cho 3 và cho 4*2); parse_F được gọi 3 lần (cho 3, 4, 2). Kết quả: 1 2 3.

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

      Một dòng duy nhất chứa một biểu thức hợp lệ theo văn phạm trên (chỉ gồm chữ số và các ký tự + - * / ( ), không có khoảng trắng).

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

      In ra một dòng gồm ba số nguyên cách nhau bởi khoảng trắng: số lần gọi parse_E, số lần gọi parse_T, số lần gọi parse_F, theo đúng thứ tự đó.

    Ví dụ:

    Đầu vào:

    3+4*2

    Đầu ra:

    1 2 3

    Đầu vào:

    3

    Đầu ra:

    1 1 1

    Đang tải editor...