## Editorial for DMOPC '19 Contest 4 P1 - Valid Strings

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

For this problem, note that the only relevant thing is whether the brackets are balanced. Since all characters are either digits or brackets, we don't care about invalid characters. Furthermore, the digits have no relevance to the solution since they can be placed anywhere without problem.

Therefore, we only have to determine if the brackets are balanced. A good way to do this is to keep track of bracket depth. Every time you encounter an open bracket, increase this counter. Every time you encounter a closed bracket, decrease this counter. If the counter is ever negative, the sequence is invalid. Also, if the counter is not at the end of the operation, the sequence lacks closing brackets, and is also invalid.

## Comments

Another possible method is using an amazing function in some languages called

`eval()`

. This is generally only available in scripting languages like Python, Ruby or JavaScript.Simply replace all open brackets with, for example

`1*(`

, all closed brackets with`)*1`

and all`()`

with`1`

, then prepend the string with`1*`

and append`*1`

, and run the`eval()`

function. Catch all exceptions, if an exception occurs, the string is invalid, otherwise it is valid.For example,

`((1))(2)`

would be`0*1*(1*(1)*1)*11*(2)*1*0`

.Its a nice trick to learn if you want to

~~solve~~cheese these kind of validation problems (try bananas!)