Rezolvare PBinfo #3991

Cerința

Fie un șir de paranteze rotunde, deschise sau închise. Putem efectua de câte ori dorim operația de transformare a unei paranteze deschise într-una închisă sau invers. Să se determine numărul minim de operații necesare transformării secvenței inițiale într-una corect parantezată. Dacă acest lucru nu este posibil, se va afișa -1.

Date de intrare

Programul citește de la tastatură șirul de paranteze rotunde, fără spații.

Date de ieșire

Programul va afișa pe ecran numărul minim de operații necesar pentru a transforma șirul într-o secvență corect parantezată. Dacă nu este posibilă parantezarea corectă, se va afișa -1.

Restricții și precizări

• 1 ≤ numărul de paranteze ≤ 1000

Exemplul 1:

Intrare

((((

Ieșire

2

Explicație

O posibilitate este să modificăm ultimele două paranteze deschise în paranteze închise și să obținem (()).

Exemplul 2:

Intrare

)

Ieșire

-1

Explicație

Nu putem obține o expresie corect parantezată.

Exemplul 3:

Intrare

((()()()

Ieșire

1

Explicație

A doua paranteză se transformă în paranteză închisă.