Bessie essaie de taper une chaîne de parenthèses équilibrée sur son nouvel ordinateur portable, mais ses grands sabots la rendent maladroite et elle se trompe. Trouvez le nombre minimal de caractères à inverser (ouvrante en fermante ou l’inverse) pour équilibrer la chaîne.

Il existe plusieurs définitions de l’équilibre. La plus simple impose autant d’ouvrantes que de fermantes au total, et au moins autant d’ouvrantes que de fermantes dans chaque préfixe. Les chaînes suivantes sont équilibrées :

()
(())
()(()())

Celles-ci ne le sont pas :

)(
())(
((())))

Entrée

• Ligne 1 : une chaîne de parenthèses $A$ de longueur paire, au plus 100,000 caractères.

Sortie

• Ligne 1 : un entier, le nombre minimal de parenthèses à inverser pour équilibrer la chaîne.

Exemples

Entrée 1

())(

Sortie 1

2

Remarque

Il faut inverser la dernière parenthèse et l’une des deux fermantes du milieu.

Auteur : Brian Dean, 2012