Cho một biểu thức số học ở dạng tiền tố (prefix), hãy dựng cây cú pháp trừu tượng (AST) tương ứng, trong đó mỗi toán tử là một nút trong (có đúng 2 con) và mỗi toán hạng là một nút lá.
Yêu cầu tính:
Ví dụ: với biểu thức tiền tố + a * b c, cây AST là nút gốc + có con trái là lá a, con phải là nút * với hai con lá b, c. Chiều cao =2, số lá =3.
Một dòng duy nhất chứa biểu thức tiền tố, các token (toán tử và toán hạng) cách nhau bởi đúng một khoảng trắng. Toán tử nhị phân thuộc tập {+,−,∗,/,∧} (ký hiệu ^ cho lũy thừa). Toán hạng là một chữ cái thường (a-z, biến) hoặc một số nguyên không âm (có thể nhiều chữ số). Đề bài đảm bảo biểu thức tiền tố hợp lệ (parse được thành đúng một cây).
In ra một dòng gồm hai số nguyên cách nhau bởi một khoảng trắng: chiều cao của cây và số lá của cây.
Ví dụ với input + a * b c, output là 2 3.
Ví dụ:
Đầu vào:
+ a b
Đầu ra:
1 2
Đầu vào:
a
Đầu ra:
0 1
Đang tải editor...