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] Xây dựng AST từ biểu thức trung tố và in dạng tiền tố

    Cho một biểu thức số học viết dưới dạng trung tố (infix), gồm số nguyên không âm, biến (một chữ cái thường), các toán tử hai ngôi +, -, *, /, ^ (lũy thừa) và dấu ngoặc đơn (, ). Độ ưu tiên các toán tử theo quy ước chuẩn: ^ cao nhất và kết hợp phải (right-associative), tiếp theo là *, / (kết hợp trái), thấp nhất là +, - (kết hợp trái). Biểu thức không có toán tử một ngôi (không có dấu trừ đơn).

    Hãy dựng AST của biểu thức (tuân theo đúng độ ưu tiên và tính kết hợp trên) rồi in ra biểu diễn tiền tố đầy đủ ngoặc của AST: mỗi lá in ra chính token của nó; mỗi nút trong in ra dạng (op left right) với op là ký tự toán tử, left, right là biểu diễn (đệ quy) của hai cây con, các thành phần cách nhau đúng một dấu cách.

    Ví dụ: 2+3*4 →\to→ (+ 2 (* 3 4)). 2^3^2 (kết hợp phải, nghĩa là 2(32)2^{(3^2)}2(32)) →\to→ (^ 2 (^ 3 2)).

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

      Một dòng duy nhất, là chuỗi biểu thức không chứa khoảng trắng, chỉ gồm các ký tự: chữ số 0-9 (số nguyên không âm, có thể nhiều chữ số), chữ cái thường (mỗi biến là đúng một chữ cái), và các ký tự + - * / ^ ( ). Biểu thức đảm bảo hợp lệ về cú pháp và về ngoặc.

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

      In ra trên một dòng chuỗi biểu diễn tiền tố đầy đủ ngoặc của AST tương ứng, đúng định dạng đã mô tả.

    Ví dụ:

    Đầu vào:

    2^3^2

    Đầu ra:

    (^ 2 (^ 3 2))

    Đầu vào:

    2+3*4

    Đầu ra:

    (+ 2 (* 3 4))

    Đang tải editor...