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 phân tích đệ quy

    Xét văn phạm biểu thức số học trung tố (các số là số nguyên không âm, có thể nhiều chữ số, không có khoảng trắng):

    E→T ((+∣−) T)∗E \to T\ \big((+|-)\ T\big)^*E→T ((+∣−) T)∗ T→F ((∗∣/) F)∗T \to F\ \big((*|/)\ F\big)^*T→F ((∗∣/) F)∗ F→num ∣ ( E )F \to \text{num} \ \mid\ ( \ E \ )F→num ∣ ( E )

    Hãy cài đặt bộ phân tích cú pháp đệ quy xuống cho văn phạm trên; mỗi hàm (EEE, TTT, FFF) khi phân tích xong các toán hạng con của nó thì phát ra (emit) token tương ứng theo đúng thứ tự hậu tố (postfix / Reverse Polish Notation - RPN): với mỗi phép toán, hai toán hạng được phát ra trước, rồi mới đến ký hiệu phép toán.

    Yêu cầu: in ra dãy token hậu tố thu được, cách nhau bởi đúng một khoảng trắng.

    Ví dụ: với E=E = E= 12+3*(45-6), dãy hậu tố là 12 3 45 6 - * +.

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

      Một dòng chứa biểu thức EEE (1≤∣E∣≤20001 \le |E| \le 20001≤∣E∣≤2000), gồm các chữ số 0-9, các ký tự + - * / ( ), không có khoảng trắng, được đảm bảo hợp lệ cú pháp theo văn phạm trên (các số nguyên không có số 0 ở đầu ngoại trừ số 0 chính nó).

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

      In ra một dòng chứa các token hậu tố (số hoặc toán tử), cách nhau bởi một khoảng trắng.

    Ví dụ:

    Đầu vào:

    12+3*(45-6)

    Đầu ra:

    12 3 45 6 - * +

    Đầu vào:

    42

    Đầu ra:

    42

    Đang tải editor...