Bài tập | NEU OJ

Loại bỏ biểu thức con chung (Common Subexpression Elimination – CSE) là một tối ưu hoá quan trọng: nếu hai nút trên AST biểu diễn cùng một cấu trúc biểu thức con (cùng toán tử/toán hạng, cùng cách sắp xếp trái–phải), trình biên dịch chỉ cần tính một lần rồi tái sử dụng kết quả.

Cho một biểu thức tiền tố với toán tử hai ngôi $+, -, \times, \div$ và toán hạng là biến (một chữ cái thường) hoặc hằng số nguyên không âm. Với mỗi nút của AST (kể cả lá), gọi dạng chuẩn tắc của nó là biểu diễn tiền tố đầy đủ của cây con gốc tại nút đó (ví dụ cây con $a\times b$ có dạng chuẩn tắc là chuỗi (* a b)). Hai nút được xem là cùng một biểu thức con khi và chỉ khi dạng chuẩn tắc của chúng giống hệt nhau về chuỗi ký tự (không áp dụng tính giao hoán, tức $a+b$ và $b+a$ được coi là khác nhau).

Hãy tính:

Tổng số nút của AST (kể cả lá và toán tử),
Số biểu thức con duy nhất (số dạng chuẩn tắc phân biệt xuất hiện trong cây),
Số lần xuất hiện nhiều nhất của một biểu thức con bất kỳ trong cây.

Đị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ệ 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ự: tổng số nút, số biểu thức con duy nhất, số lần xuất hiện nhiều nhất của một biểu thức con.

Ví dụ: với input + * a b * a b (tức $(a\times b) + (a\times b)$ ), cây có 7 nút; các dạng chuẩn tắc phân biệt là a, b, (* a b), (+ (* a b) (* a b)) — tức 4 biểu thức con duy nhất; biểu thức con xuất hiện nhiều nhất là a, b hoặc (* a b), mỗi cái xuất hiện 2 lần. Output: 7 4 2.

solution

Đề bài: [Trình biên dịch] Đếm biểu thức con trùng lặp trên cây cú pháp (CSE)