Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Người ta định nghĩa một dãy ngoặc đúng theo đệ quy như sau:

- xâu A là xâu rỗng là một dãy ngoặc đúng
- Nếu xâu A là dãy ngoặc đúng thì (A) cũng là dãy ngoặc đúng
- Nếu xâu A và xâu B là dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.

Còn những xâu chứa những ký tự khác "(" và ")" được gọi là xâu không hợp lệ.

Ví dụ:

S = "(A()B)" là dãy "KHONG HOP LE" vì chứa chữ cái A và B

S = "()()(())" là dãy ngoặc "DUNG"

S = "()())" là dãy ngoặc "KHONG DUNG"

Cho xâu S. Hãy kiểm tra xâu S là dãy ngoặc "DUNG", "KHONG DUNG" hay là xâu "KHONG HOP LE"

Ví dụ 1:

Input
(A()B)

Output
KHONG HOP LE

Ví dụ 2:

Input
()()(())

Output
DUNG

Ví dụ 2:

Input
((())

Output
KHONG DUNG