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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nvatuan
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:

  1. Là một chuỗi rỗng.
  2. 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).
  3. 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.

Input

  • 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)\)

Output

  • \(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.

Example

Test 1

Input 
3
{[()]}
{[(])}
{{[[(())]]}}
Output 
YES
NO
YES

Bình luận