(7 ĐIỂM) DÃY NGOẶC ĐÚNG NGƯỜI TA ĐỊNH NGHĨA MỘT XÂU KÍ TỰ GỒM CÁC KÍ...

Bài 3: (7 điểm) Dãy ngoặc đúng

Người ta định nghĩa một xâu kí tự gồm các kí tự ‘(’ và ‘)’ là một dãy ngoặc đúng như sau:

- Xâu rỗng là một dãy ngoặc đúng.

- Nếu X là dãy ngoặc đúng thì (X) cũng là một dãy ngoặc đúng

- Nếu X, Y là những dãy ngoặc đúng thì XY cũng là dãy ngoặc đúng.

Những dãy ngoặc sau là những dãy ngoặc đúng:

- ()(())

- ((()))

Những dãy ngoặc sau thì không:

- )(

- (((()))

- )()()(

Cho một xâu kí tự T = T

, T

, ..T

, trong đó T

là một trong hai kí tự ‘(’ hoặc ‘)’ với mọi i=1..n.

Yêu cầu: Hãy đếm số cặp i,j (i<j) mà xâu kí tự thu được từ việc ghép các kí tự liên tiếp T

, T

, ..T

(giữ nguyên thứ tự) là một dãy ngoặc đúng.

Dữ liệu vào: File văn bản BAI3.INP gồm 2 dòng:

- Dòng thứ nhất chứa số n là độ dài của xâu kí tự T (n ≤ 1000).

- Dòng thứ 2 chứa xâu kí tự T

Dữ liệu ra: Ghi ra file văn bản BAI3.OUT một số duy nhất là kết quả tìm được.

Ví dụ:

BAI3.INP BAI3.OUT

10

5

(()())(()(

Cán bộ coi thi không giải thích gì thêm.