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] Chuyển trung tố sang hậu tố bằng cây 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)

    Hãy cài đặt bộ phân tích cú pháp đệ quy cho văn phạm trên; mỗi khi một hàm hoàn tất việc khớp một toán tử (ở vòng lặp * của EEE hoặc TTT), hãy sinh (emit) toán tử đó ngay sau khi hai toán hạng liên quan đã được sinh — đây chính là phép duyệt hậu thứ tự (postorder) trên cây phân tích cú pháp, cho kết quả là dạng hậu tố (postfix) của biểu thức. Dữ liệu vào đảm bảo luôn đúng văn phạm, không có khoảng trắng trong mỗi biểu thức.

    Ví dụ: biểu thức 3+4*2 có cây phân tích với gốc là phép +, cây con trái là lá 3, cây con phải là cây phép * (con trái 4, con phải 2). Duyệt postorder cho kết quả 3 4 2 * +.

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

      Dòng đầu tiên chứa số nguyên nnn (1≤n≤201 \le n \le 201≤n≤20) — số lượng biểu thức. nnn dòng tiếp theo, mỗi dòng là 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 nnn dòng, dòng thứ iii là dạng hậu tố của biểu thức thứ iii, các token cách nhau bởi đúng một khoảng trắng.

    Ví dụ:

    Đầu vào:

    1
3+4*2

    Đầu ra:

    3 4 2 * +

    Đầu vào:

    1
(1+2)*(3+4)

    Đầu ra:

    1 2 + 3 4 + *

    Đang tải editor...