solution

Khi một trình biên dịch cần hiện lại (pretty-print) mã nguồn từ cây cú pháp (ví dụ để báo lỗi hoặc tối ưu hoá), nó phải chèn dấu ngoặc đơn đúng vị trí cần thiết — thừa hoặc thiếu dấu ngoặc đều làm sai nghĩa biểu thức.

Cho một biểu thức hậu tố mà toán hạng là các chữ cái thường phân biệt (a-z), toán tử hai ngôi thuộc $\{+, -, \times, \div\}$ (viết + - * /), trong đó $\{+,-\}$ có độ ưu tiên thấp hơn $\{\times,\div\}$, tất cả đều kết hợp trái (left-associative). Hãy dựng cây cú pháp tương ứng và in ra biểu thức trung tố (infix) tương đương với đúng cấu trúc cây đó (tức giữ nguyên thứ tự thực hiện phép toán), sử dụng số lượng dấu ngoặc đơn ít nhất có thể — chỉ thêm ngoặc khi không thêm sẽ làm thay đổi thứ tự tính toán so với cây gốc.

Không có khoảng trắng nào trong biểu thức trung tố kết quả.

Ví dụ: hậu tố a b c - - ứng với cây $a - (b - c)$ (khác với $a-b-c$), nên kết quả in ra là a-(b-c). Ngược lại hậu tố a b - c - ứng với $(a-b)-c$, in ra a-b-c (không cần ngoặc vì kết hợp trái đã đúng thứ tự mặc định).