THỰC HÀNH

Cho một xâu ký tự chỉ gồm các ký tự mở ngoặc “{” và đóng ngoặc “}”. Ta xét định nghĩa dãy ngoặc đúng như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng.
• X là một dãy ngoặc đúng nếu và chỉ nếu X có dạng {Y} hoặc YZ trong đó Y, Z là các dãy ngoặc đúng.

Chẳng hạn dãy ngoặc “{}{{}{}}” là dãy ngoặc đúng, các dãy ngoặc “}{”, “{{}{” là các dãy ngoặc không đúng.

Dữ liệu vào:

Gồm một dòng duy nhất là một xâu ký tự chỉ chứa các ký tự “{” và “}”.

Dữ liệu ra:

Ghi “YES” nếu xâu tương ứng là dãy ngoặc đúng, “NO” nếu ngược lại.

Ví dụ:

Dữ liệu vào:
{{}{}}

Dữ liệu ra:
YES

Dữ liệu vào:
{{}{{}

Dữ liệu ra:
NO

Giới hạn:

• 50% số test (ứng với 40% số điểm của bài) có dữ liệu vào là một xâu có độ dài không quá 255 ký tự.
• 50% số test còn lại (ứng với 50% số điểm của bài) có dữ liệu vào là một xâu có độ dài không quá 10⁵ ký tự.