Mismatched Brackets
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- BRACKETS2
- 1000ms
- 65536kb
- 12960
- 4190 (32%)
-
- 출처
- 분류
문제
Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas have problems: some of the brackets are mismatched! Since there are so many formulas in his paper, he decided to check their validity with a computer program.
The following kinds of brackets are included in Best White’s paper.
- Round brackets are opened by a
(
and closed by a)
. - Curly brackets are opened by a
{
and closed by a}
. - Square brackets are opened by a
[
and closed by a]
.
A formula is said well-matched when the following conditions are met:
- Every bracket has a corresponding pair.
(
corresponds to)
,[
corresponds to]
, et cetera. - Every bracket pair is opened first, and closed later.
- No two pairs "*cross*" each other. For example,
[(])
is not well-matched.
Write a program to help Best White by checking if each of his formulas is well-matched. To make the problem easier, everything other than brackets are removed from the formulas.
입력
The first line of the input will contain the number of test cases C\ (1 \le C \le 100). Each test is given in a single line as a character string. The strings will only include characters in "[](){}
" (quotes for clarity). The length of the string will not exceed 10,000.
출력
For each test case, print a single line "YES
" when the formula is well-matched; print "NO
" otherwise. (quotes for clarity)
예제 입력
3 ()() ({[}]) ({}[(){}])
예제 출력
YES NO YES
노트