Bài tập | NEU OJ

Cho văn phạm biểu thức số học với dấu trừ một ngôi:

\begin{aligned} E &\to T\ ((\,{+}\mid{-}\,)\ T)^* \\ T &\to U\ ((\,{*}\mid{/}\,)\ U)^* \\ U &\to {-}\ U \mid F \\ F &\to (\ E\ ) \mid \text{số nguyên không âm} \end{aligned}

trong đó các vòng lặp $(\dots)^*$ ở $E$ và $T$ được xây dựng cây cú pháp (AST) kết hợp trái (left-associative): ví dụ 1+2+3 dựng thành $((1+2)+3)$ , không phải $(1+(2+3))$ .

Viết bộ phân tích cú pháp đệ quy để: (1) dựng cây cú pháp trừu tượng (AST) của biểu thức theo đúng văn phạm và quy tắc kết hợp trên, rồi (2) in biểu thức tương ứng dưới dạng đầy đủ dấu ngoặc (fully parenthesized), trong đó mỗi phép toán hai ngôi được bọc trong một cặp ngoặc (...), và dấu trừ một ngôi được in dưới dạng (-X). Số nguyên được in nguyên văn như trong đầu vào (không thêm/bớt chữ số). Các cặp ngoặc ( ) vốn có trong biểu thức đầu vào chỉ dùng để xác định thứ tự thực hiện phép toán khi dựng AST — chúng không được giữ nguyên vị trí trong kết quả in ra, kết quả chỉ chứa các ngoặc sinh ra từ chính các nút của AST.

Ví dụ: với đầu vào 3*-4-5, cây được dựng là $(3 \times (-4)) - 5$ , in ra ((3*(-4))-5).

Định dạng đầu vào:
Một dòng duy nhất chứa biểu thức, gồm chữ số 0-9 (số nguyên không âm, có thể nhiều chữ số, không có số 0 đứng đầu ngoại trừ chính số 0), các toán tử + - * /, dấu ngoặc ( ), không chứa dấu cách, đảm bảo hợp lệ theo văn phạm trên. Độ dài không quá 300 ký tự.
Định dạng đầu ra:
Một dòng duy nhất — biểu thức dạng đầy đủ dấu ngoặc như mô tả ở trên (không có dấu cách nào trong chuỗi kết quả).

solution

Đề bài: [Trình biên dịch] In biểu thức dạng đầy đủ dấu ngoặc từ cây cú pháp