Mô tả
Chị Lan làm kế toán tại nhà máy sữa Vinamilk. Mỗi cuối tháng, chị phải dựng rất nhiều công thức Excel phức tạp để tổng hợp chi phí sản xuất. Do công thức dài ngoằng, chị thỉnh thoảng quên đóng hoặc mở ngoặc khiến Excel báo lỗi #REF!.
Hôm nay, bạn hãy viết một chương trình nhỏ giúp chị Lan kiểm tra xem một chuỗi công thức chỉ chứa dấu ngoặc tròn ( và ) cần phải chèn thêm ít nhất bao nhiêu dấu ngoặc để trở thành một công thức hợp lệ.
Một công thức hợp lệ là công thức thỏa mãn hai điều kiện:
- Mỗi dấu đóng ngoặc
)phải khớp đúng với một dấu mở ngoặc(đứng trước nó. - Khi duyệt từ trái sang phải, số lượng dấu mở ngoặc không bao giờ nhỏ hơn số lượng dấu đóng ngoặc tại bất kỳ thời điểm nào.
Ví dụ ((())) và ()() là công thức hợp lệ, còn ())( và (() thì chưa hợp lệ.
Đầu vào
Một chuỗi s gồm nhiều ký tự, mỗi ký tự chỉ là ( hoặc ).
Đầu ra
In ra một số nguyên duy nhất là số lượng dấu ngoặc tối thiểu cần chèn thêm để chuỗi hợp lệ.
Ràng buộc
- Độ dài chuỗi
nthỏa mãn1 ≤ n ≤ 10^5.
Ví dụ
Input:
())(
Output:
2
Giải thích:
Xét từng bước duyệt chuỗi ())(:
- Ký tự
(: Đang có 1 dấu mở chưa khớp. - Ký tự
): Khớp với dấu mở trước đó, hiện còn 0 dấu mở. - Ký tự
): Không còn dấu mở nào để khớp, ta bắt buộc phải chèn thêm 1 dấu(ở phía trước nó. Số lần chèn là 1. - Ký tự
(: Còn lại 1 dấu mở chưa khớp ở cuối, ta lại phải chèn thêm 1 dấu)ở phía sau nó. Số lần chèn là 2. Tổng cộng cần chèn thêm 2 dấu ngoặc để chuỗi()()()trở nên hợp lệ.