DMOPC '19 Contest 4 P1 - Valid Strings

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M
Authors:
richardzhang, little_prince
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:

  1. Nothing (an empty string).
  2. A non-negative integer expressed in decimal digits (e.g. 5, 230, 0032), optionally followed by another valid string.
  3. 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 strings. For each string, s_1, s_2, \dots, s_N, output on the ith line, the validity of the ith string. If the string is valid, output YES. If the string is invalid, output NO. The length in characters of each string, s_i, is guaranteed to be in the range [1,1000].

Constraints

In all tests,
1 \le N \le 100

Input Specification

The first line contains one number, N.
The following N lines each contain one string s_i.

Output Specification

Output the validity of the ith string on the ith line.

Sample Input

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

Sample Output

YES
YES
YES
YES
NO
NO
NO

Comments