Bài tập | NEU OJ

Cho một biểu thức số học viết dưới dạng ký pháp tiền tố (prefix), gồm các toán tử hai ngôi $+, -, \times, \div$ và các toán hạng là biến (một chữ cái thường a-z) hoặc hằng số nguyên không âm. Ký pháp tiền tố tương ứng một-một với cây cú pháp AST: mỗi toán tử là một nút trong (có đúng 2 con), mỗi toán hạng là một nút lá.

Hãy dựng AST tương ứng và tính:

Số nút lá (toán hạng),
Số nút trong (toán tử),
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 chỉ gồm 1 lá có chiều cao $0$ ).

Định dạng đầu vào:
Một dòng duy nhất chứa các token của biểu thức tiền tố, cách nhau bởi khoảng trắng. Biểu thức luôn hợp lệ (đúng cú pháp tiền tố nhị phân) và không rỗng.
Định dạng đầu ra:
In ra 3 số nguyên trên một dòng, cách nhau bởi một khoảng trắng, theo thứ tự: số nút lá, số nút trong, chiều cao.

Ví dụ: với input + a * b c (tương ứng $a + (b \times c)$ ), cây có 3 lá ( $a,b,c$ ), 2 nút trong ( $+,\times$ ), chiều cao $2$ , nên output là 3 2 2.

solution

Đề bài: [Trình biên dịch] Đếm nút lá, nút trong và chiều cao của cây cú pháp