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

Để giải bài toán này, chúng ta cần kiểm tra ba điều kiện khác nhau cho chuỗi S:

1. Xác định tính hợp lệ của chuỗi: Chuỗi chỉ được chứa hai ký tự `'('` và `')'`. Nếu chuỗi chứa bất kỳ ký tự nào khác, nó sẽ được coi là "KHONG HOP LE".

2. Kiểm tra tính đúng đắn của dãy ngoặc: Điều này được thực hiện bằng cách kiểm tra rằng số lượng dấu `'('` phải bằng số lượng dấu `')'` và lúc kiểm tra, số lượng dấu `'('` không bao giờ nhỏ hơn số lượng dấu `')'` tại bất kỳ thời điểm nào khi ta duyệt chuỗi từ trái sang phải.

3. Kết quả trả về:
- Nếu chuỗi không hợp lệ, xuất "KHONG HOP LE".
- Nếu dãy ngoặc hợp lệ, xuất "DUNG".
- Nếu dãy ngoặc không hợp lệ, xuất "KHONG DUNG".

Dưới đây là quy trình chi tiết để giải quyết bài toán:

1. Đọc chuỗi S từ tệp đầu vào.
2. Khởi tạo biến `left` để đếm số lượng dấu `'('`, và biến `right` để đếm số lượng dấu `')'`.
3. Duyệt từng ký tự trong chuỗi:
- Nếu ký tự là `'('`, tăng `left` lên 1.
- Nếu ký tự là `')'`, tăng `right` lên 1.
- Nếu ký tự khác, in "KHONG HOP LE" và dừng kiểm tra.
- Nếu tại bất kỳ thời điểm nào `right` lớn hơn `left`, in "KHONG DUNG" và dừng kiểm tra.
4. Sau khi duyệt xong chuỗi:
- Nếu `left` và `right` bằng nhau, in "DUNG".
- Nếu không, in "KHONG DUNG".

Ví dụ kiểm tra với từng chuỗi:
- Với chuỗi `"(A()B)"`: chứa chữ cái 'A' và 'B', nên sẽ in "KHONG HOP LE".
- Với chuỗi `"()()(())"`: số lượng dấu mở và đóng bằng nhau và không có dấu chưa đóng, nên in "DUNG".
- Với chuỗi `"((())"`: số lượng dấu mở nhiều hơn đóng, đặt `right` lớn hơn `left` tại một thời điểm nên in "KHONG DUNG".

Dưới đây là mã giả cho thuật toán này:

```
def check_parentheses(S):
left = 0
right = 0

for char in S:
if char == '(':
left += 1
elif char == ')':
right += 1
else:
return "KHONG HOP LE"

if right > left:
return "KHONG DUNG"

if left == right:
return "DUNG"
else:
return "KHONG DUNG"

# Đọc nhập liệu
S = input()
result = check_parentheses(S)

# Xuất kết quả
print(result)
```

Cách tiếp cận này hiệu quả với độ phức tạp O(n), với n là độ dài của chuỗi S, do chúng ta chỉ duyệt chuỗi một lần.