Một tối ưu hóa nhỏ mà trình biên dịch có thể làm ở giai đoạn phân tích cú pháp là loại bỏ các cặp ngoặc đơn dư thừa (không ảnh hưởng đến cách nhóm các toán hạng/toán tử) trước khi dựng cây cú pháp, giúp cây gọn hơn.
Cho một biểu thức trung tố hợp lệ, cân bằng ngoặc, toán hạng là một chữ số (0-9), toán tử là + - * /. Một cặp ngoặc ( ... ) tương ứng được xác định là DƯ THỪA theo đúng thuật toán sau (dùng ngăn xếp — stack):
), đẩy (push) nó vào ngăn xếp.): lần lượt lấy ra (pop) các phần tử trên đỉnh ngăn xếp cho tới khi gặp và lấy luôn dấu ( tương ứng. Gọi k là số phần tử đã lấy ra, KHÔNG TÍNH dấu ( vừa lấy cuối cùng. Nếu k<2 (nghĩa là bên trong cặp ngoặc này chỉ có đúng một phần tử — một toán hạng đơn hoặc một nhóm đã từng được xử lý trước đó — chứ không có toán tử nào tách biệt hai phần) thì cặp ngoặc này là dư thừa, tăng biến đếm lên 1.(...) như một toán hạng gộp), rồi tiếp tục duyệt phần còn lại của chuỗi.Hãy đếm tổng số cặp ngoặc dư thừa theo đúng thuật toán trên.
Ví dụ: ((1)) có 2 cặp ngoặc dư thừa: cặp trong cùng bao quanh một toán hạng đơn 1 (k=1<2), và sau khi thay bằng ký hiệu gộp, cặp ngoài cũng chỉ bao quanh đúng một phần tử (k=1<2).
Một dòng duy nhất chứa biểu thức, không có khoảng trắng, chỉ gồm các chữ số 0-9, các toán tử + - * / và dấu ngoặc ( ), đảm bảo cân bằng và đúng cú pháp.
In ra một dòng duy nhất là một số nguyên — tổng số cặp ngoặc dư thừa.
Ví dụ:
Đầu vào:
((1+2))
Đầu ra:
1
Đầu vào:
(1+2)
Đầu ra:
0
Đang tải editor...