solution

Ngược với bài toán chuyển trung tố sang hậu tố, đôi khi trình biên dịch cần làm điều ngược lại: từ mã trung gian dạng hậu tố (ví dụ khi hiện thực một bộ decompiler hoặc khi in biểu thức để gỡ lỗi — debug print), ta cần dựng lại cây cú pháp (expression tree) và in ra dạng trung tố.

Cho một biểu thức hậu tố hợp lệ, toán hạng là một chữ cái thường, toán tử là $+, -, \times, \div$ (+ - * /). Hãy dựng cây biểu thức và in ra dạng trung tố đầy đủ ngoặc — nghĩa là MỌI phép toán hai ngôi, không phân biệt độ ưu tiên, đều được bao bởi một cặp ngoặc đơn ( ). Nếu biểu thức chỉ có một toán hạng (không có toán tử nào), in ra toán hạng đó, không kèm ngoặc.

Ví dụ: hậu tố a b c + * (nghĩa là $a \times (b+c)$) $\to$ in ra (a*(b+c)).