teddy online judge

92. Observando Identidad Gramatical

Limite de tiempo : 1 seg.   Total runs : 138  Aceptados : 44

Y así fue como se te encargó tu primer trabajo en la Industria de Tecnologías para Calculadoras (ITC): un validador de expresiones matemáticas para calculadoras para evitar errores en otros módulos. Uno de los problemas más comunes es que a la gente se le olvida cerrar los paréntesis en una expresión. Entonces algo como

((a*b-[c/d]*[a-{15+2}))

generaría un error (pues no se cerró el último corchete). Decides empezar con un validador de paréntesis, así que solo nos enfocaremos a expresiones formadas por los siguientes caracteres: "()[]{}". Lo que tienes que validar es que no cierres un paréntesis/corchete/llave que no has abierto, no dejar un paréntesis/corchete/llave abierto cuando vas a cerrar otro, y que no dejes paréntesis/corchetes/llaves abiertas al terminar la cadena. Dicho de una manera más formal, estas son las expresiones válidas

• La cadena vacía es una expresión válida
• Si A y B son expresiones válidas, entonces AB es una expresión válida.
• Si A es una expresión válida, entonces (A), [A], {A} son expresiones válidas
• Ninguna otra cadena es una expresión válida.

Entrada

La primer línea de la entrada contiene un entero N_c (1 ≤ N_c ≤ 100), que contiene el número de casos de prueba. Las siguientes N_c líneas contienen una cadena formada por los caracteres "()[]{}". Dicha cadena tendrá una longitud mínima de 1 y máxima de 100,001.

Salida

Para cada caso de prueba, imprime una línea con el número del caso, seguido de "Valido" si la cadena es válida o "Invalido" en el caso contrario. Sigue el formato de ejemplo.

Entrada/Salida de ejemplo

3
()
[()]{}
(([][{}))

Caso 1: Valido
Caso 2: Valido
Caso 3: Invalido