Xử lý chuỗi
Mô tả
Tại phòng vận hành mạng Opennet, chị Lan thường xuyên kiểm tra các chuỗi bản tin bắt tay của modem GPON. Mỗi bản tin chứa nhiều thông điệp điều khiển, trong đó các khối thông điệp được bọc bằng cặp ngoặc tròn ( và ). Một bản tin hợp lệ khi mọi ngoặc mở đều có ngoặc đóng khớp ở đúng thứ tự, và không có ngoặc đóng thừa. Bên cạnh đó, kỹ sư mạng còn quan tâm đến độ sâu lồng nhau lớn nhất, tức số lớp ngoặc bao quanh một vị trí nhiều nhất, để đánh giá mức phức tạp cấu trúc bản tin. Nhiệm vụ của bạn là viết chương trình cho chị Lan: cho một chuỗi chỉ gồm ( và ), hãy xác định chuỗi đó có hợp lệ hay không. Nếu hợp lệ, trả thêm độ sâu lớn nhất; nếu không hợp lệ, trả về -1.
Đầu vào
- Một chuỗi
sduy nhất gồm các ký tự(và), độ dài từ0đến100000.
Đầu ra
- Một số nguyên trên một dòng: nếu chuỗi hợp lệ, in ra độ sâu lồng nhau lớn nhất (chuỗi rỗng có độ sâu
0); nếu không hợp lệ, in ra-1.
Ràng buộc
0 ≤ độ dài s ≤ 100000.- Chuỗi
schỉ chứa ký tự(hoặc).
Ví dụ
Ví dụ 1:
- Đầu vào:
((())()) - Đầu ra:
3 - Giải thích: Chuỗi hợp lệ. Vị trí thứ ba (tính từ 1) nằm trong ba lớp ngoặc, nên độ sâu lớn nhất là
3.
Ví dụ 2:
- Đầu vào:
(() - Đầu ra:
-1 - Giải thích: Có hai ngoặc mở nhưng chỉ một ngoặc đóng, thiếu một ngoặc đóng nên chuỗi không hợp lệ.
Ví dụ 3:
- Đầu vào:
)()( - Đầu ra:
-1 - Giải thích: Ngoặc đóng đầu tiên không có ngoặc mở tương ứng trước nó, nên chuỗi không hợp lệ.