solution

Trong trình biên dịch, biểu thức thường được biểu diễn nội bộ dưới dạng cây biểu thức (expression tree/AST): mỗi lá là một toán hạng, mỗi nút trong là một toán tử hai ngôi với con trái/con phải là hai toán hạng con của nó. Biểu thức hậu tố tương ứng chính là kết quả duyệt cây theo thứ tự hậu thứ tự (post-order).

Cho một biểu thức hậu tố hợp lệ, toán hạng là số nguyên hoặc biến (một chữ cái thường a-z), toán tử hai ngôi $+,-,\times,\div,\hat{}$ (+ - * / ^). Hãy dựng cây biểu thức tương ứng rồi in ra:

1. Biểu thức tiền tố (prefix, duyệt tiền thứ tự) tương ứng.
2. Chiều cao của cây, quy ước cây chỉ có một nút (một lá duy nhất) có chiều cao $0$, chiều cao của một nút trong bằng $1 + \max$ chiều cao hai cây con.
3. Số lá (số toán hạng) của cây.

Ví dụ: hậu tố a b + c * có cây với gốc *, con trái là cây con +(a,b), con phải là lá c; tiền tố là * + a b c, chiều cao $2$, số lá $3$.