Một trạm quan sát thiên văn vừa nhận được một chuỗi tín hiệu lạ từ ngoài không gian, ký hiệu là chuỗi . Các nhà khoa học phát hiện ra rằng chuỗi tín hiệu này chỉ bao gồm hai loại ký tự là ( và ). Để xác định xem đây có phải là một thông điệp có cấu trúc hoàn chỉnh hay chỉ là nhiễu sóng, họ cần kiểm tra tính hợp lệ của dãy ngoặc này.
Một tín hiệu được coi là "hoàn chỉnh" (đúng) nếu mỗi ký tự mở ( đều có một ký tự đóng ) tương ứng theo đúng thứ tự lồng nhau hoặc liên tiếp (nguyên lý Stack). Hãy xác định trạng thái của tín hiệu.
Dữ liệu:
Dòng đầu chứa số nguyên là số tín hiệu cần kiểm tra.
dòng sau, mỗi dòng chứa chuỗi ký tự (độ dài của chuỗi ) là một tín hiệu cần kiểm tra.
Kết quả: Với mỗi tín hiệu cần kiểm tra, in ra YES nếu tín hiệu là dãy ngoặc đúng, ngược lại in ra NO.
