The Interview Problem

시간 제한1초메모리 제한2048 MB

요약

괄호 문자열을 만들면서 숫자가 나올 때마다 그만큼 문자를 지울 수 있을 때, 균형 잡힌 괄호열을 만들 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 그리디, 스택, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

You are given a string $s$ consisting of parentheses ("(" and ")") and digits ("0" through "9"). From the string $s$ , you construct another string $t$ by considering every character of $s$ in order and performing the following operations based on the character values:

"(": append "(" to $t$ .
")": append ")" to $t$ .
$0 \leq c \leq 9$ : delete any $c$ characters from $t$ . It is guaranteed that it is always possible to do so. The deleted characters don't need to be consecutive.

Is it possible to construct $t$ to be a balanced bracket sequence?

입력

The first line contains an integer $t$ ( $1 \leq t \leq 10^{4}$ ), the number of test cases.

For each test case, you are given a non-empty string $s$ consisting of parentheses and digits ("()0123456789"). The length of the string will be at most $3 \cdot 10^{5}$ characters.

It is guaranteed that the total length of the strings will not exceed $3 \cdot 10^{5}$ characters.

출력

For each test case, output "YES" if it is possible to construct $t$ to be a balanced bracket sequence, and "NO" otherwise.

You may output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

예제2

예제 1
입력
```
2
((()(3)1
(()1)
```
예상 출력
```
Yes
No
```

예제 2

입력

5
()1()
(())
()1((((2()())))3)()
((2))()
((1()))(1)()

예상 출력

No
Yes
Yes
No
Yes