DMOPC '19 Contest 4 P1 - Valid Strings

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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].


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


Sample Output