Dãy ngoặc
Xem dạng PDF
Gửi bài giải
Điểm:
10,00
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
64M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++, Python
Một dãy ngoặc đúng là một xâu gồm các ký tự "(" và ")" được định nghĩa đệ quy như sau:
- Dãy rỗng (không có ký tự nào) là một dãy ngoặc đúng.
- Nếu A là một dãy ngoặc đúng thì A – xâu tạo thành bằng cách thêm một ký tự "(" vào đầu xâu A và thêm một ký tự ")" vào cuối xâu A – là dãy ngoặc đúng.
- Nếu A và B là hai dãy ngoặc đúng thì AB – Xâu tạo thành bằng cách lấy xâu B nối vào cuối xâu A – là dãy ngoặc đúng.
- Những xâu ký tự không thể xây dựng theo cách trên không phải dãy ngoặc đúng.
Yêu cầu:
Kiểm tra một xâu ký tự có phải là dãy ngoặc đúng hay không.
Dữ liệu:
Dòng 1 chứa số ~q~ là số xâu cần kiểm tra (~q≤10~)
~q~ dòng tiếp mỗi dòng chứa một xâu ký tự độ dài không quá ~10^5~ là một xâu cần kiểm tra
Kết quả:
Ứng với mỗi xâu trong file dữ liệu, ghi ra từ YES nếu đó là một dãy ngoặc đúng, ghi ra từ NO nếu ngược lại
Input
4
(())()((()))
((())
(A)
() ()
Output
YES
NO
NO
NO
Bình luận
Thầy ơi, bài này có giải được không ạ?
Em có thể nộp bài giải tự do nhé.
Dạ, ý con là, bài này con thử nhiều lần rồi vẫn không được, và không có submission của ai khác đúng hết. Xin thầy kiểm lại bài này có vấn đề gì không, hay chỉ là chưa ai làm đúng thôi?
Do chưa xét kỹ thôi đó em!
Dạ bây giờ con giải được rồi, cảm ơn thầy đổi cái ví dụ cho rõ hơn ạ.