DMOPC '19 Contest 4 P1 - Valid Strings - DMOJ: Modern Online Judge

DMOPC '19 Contest 4 P1 - Valid Strings

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 64M

Authors:

Problem type

Veshy is entering strings into his calculator consisting of only (, ), and decimal digits; however, some strings are invalid and produce an error.

A valid string must either be:

Nothing (an empty string).
A non-negative integer expressed in decimal digits (e.g. 5, 230, 0032), optionally followed by another valid string.
A pair of brackets enclosing a valid string (e.g. (5)), also optionally followed by another valid string.

Examples of valid strings:
(1)(2), ((1))(2), 1(2), (500())

Examples of invalid strings:
(12, (1)), ((1)()

You are given $N$ $N$ strings. For each string, $s_1, s_2, \dots, s_N$ $s_{1}, s_{2}, \dots, s_{N}$ , output on the $i$ $i$ th line, the validity of the $i$ $i$ th string. If the string is valid, output YES. If the string is invalid, output NO. The length in characters of each string, $s_i$ $s_{i}$ , is guaranteed to be in the range $[1,1000]$ $[1, 1000]$ .

Constraints

In all tests,
$1 \le N \le 100$ $1 \leq N \leq 100$

Input Specification

The first line contains one number, $N$ $N$ .
The following $N$ $N$ lines each contain one string $s_i$ $s_{i}$ .

Output Specification

Output the validity of the $i$ $i$ th string on the $i$ $i$ th line.

Sample Input

Copy

7
1(2)
(1)(2)
((1))(2)
(500())
(12
(1))
((1)()

Sample Output

Copy

YES
YES
YES
YES
NO
NO
NO

Comments

5

doodlering commented on Sept. 6, 2020, 4:05 p.m.

Is ")(" a valid string?

3

maxcruickshanks commented on Sept. 7, 2020, 1:21 a.m.

No.