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

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" INPUT: NGOAC.INP: Một xâu S chứa tối đa 106 phần tử OUTPUT: NGOAC.OUT: Thông báo "KHONG HOP LE" nếu xâu không hợp lệ Thông báo "DUNG" nếu xâu đúng Thông báo "KHONG DUNG" nếu xâu không đúng Ví dụ:   INPUT    OUTPUT        (A()B)    KHONG HOP LE        ()()(())    DUNG        ((())    KHONG DUNG