Kiểm tra chuỗi ngoặc đúng

Tác giả:

Dạng bài

Điểm: 900 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một dấu ngoặc bao gồm những ký tự như sau: (, ), {, }, [, or ].

Một cặp ngoặc đúng bao gồm (), {}, []. Còn lại, những cặp ngoặc như ((, (}, [},... đều không phải là cặp ngoặc đúng.

Ta định nghĩa một chuỗi ngoặc đúng như sau:

Là một chuỗi rỗng.
Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm ở giữa một cặp ngoặc đúng. (VD: "[{}]" là đúng thì "(+[{}]+)" sẽ đúng).
Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm bên cạnh một chuỗi ngoặc đúng. (VD: "{[]}" là đúng thì "{[]}+[()]" sẽ đúng).

Đề bài cho bạn $N$ chuỗi ngoặc. Nếu chuỗi thứ $i$ là chuỗi ngoặc đúng, in ra YES, ngược lại in ra NO.

Dòng đầu tiên chứa số nguyên $N$ là số truy vấn $(1 \leq N \leq 1000)$
$N$ dòng tiếp theo, dòng thứ $i$ chứa chuỗi ký tự $S_i$, chỉ bao gồm các dấu ngoặc. $(1 \leq $ Độ dài $S_i \leq 1000)$

$N$ dòng, dòng thứ $i$ in ra YES hoặc NO tương ứng với nếu chuỗi $S_i$ là chuỗi ngoặc đúng hoặc không đúng.

Test 1

Input

3
{[()]}
{[(])}
{{[[(())]]}}

Output

YES
NO
YES

Bình luận