Từ ký pháp tiền tố của một AST nhị phân (toán tử hai ngôi thuộc {+,−,×,÷}, toán hạng là số nguyên không âm hoặc biến - một chữ cái thường), hãy xác định ba đại lượng thống kê về cấu trúc cây: số nút lá (toán hạng), số nút toán tử (nút trong), và chiều cao của cây, định nghĩa là số cạnh trên đường đi dài nhất từ gốc tới một lá (cây gồm đúng một lá có chiều cao 0).
Ví dụ: + a * b c có AST gốc +, con trái là lá a, con phải là nút * (hai lá b, c). Có 3 lá, 2 toán tử, chiều cao 2.
Một dòng duy nhất gồm các token cách nhau bởi một dấu cách. Mỗi token là toán tử +, -, *, /, hoặc một toán hạng - số nguyên không âm (không chứa dấu - để tránh nhầm với toán tử) hoặc một chữ cái thường (biến). Dãy token tạo thành đúng một AST nhị phân hợp lệ.
In ra ba số nguyên trên một dòng, cách nhau bởi một dấu cách, theo thứ tự: số nút lá, số nút toán tử, chiều cao của cây.
Ví dụ:
Đầu vào:
x
Đầu ra:
1 0 0
Đầu vào:
+ a * b c
Đầu ra:
3 2 2
Đang tải editor...