solution

Biểu thức tiền tố (prefix / Polish notation) đặt toán tử trước hai toán hạng, ví dụ + a b nghĩa là $a+b$. Đây là dạng biểu diễn không cần độ ưu tiên hay dấu ngoặc, thường gặp khi phân tích cú pháp (parsing) trong các trình biên dịch dịch trực tiếp thành cây cú pháp trừu tượng (AST) rồi duyệt cây.

Cho một biểu thức tiền tố hợp lệ, mỗi token cách nhau đúng một khoảng trắng. Toán hạng là một chữ cái thường (a-z) hoặc một số nguyên không âm; toán tử là một trong năm ký hiệu $+,\,-,\,\times,\,\div,\,\wedge$ (viết + - * / ^, trong đó ^ là lũy thừa). Hãy chuyển biểu thức trên sang biểu thức hậu tố (postfix) tương đương, giữ nguyên cấu trúc cây cú pháp (chỉ thay đổi thứ tự token), các token trong kết quả cách nhau đúng một khoảng trắng.

Ví dụ: tiền tố * + a b - c d (nghĩa là $(a+b)\times(c-d)$) chuyển thành hậu tố a b + c d - *.