Correggere la sequenza di parentesi
Data una stringa
s composta da parentesi aperte e chiuse, è consentito modificare alcune parentesi aperte in chiuse, oppure alcune chiuse in aperte. Quante operazioni sono necessarie al minimo per rendere la sequenza di parentesi valida?Input
L'unica riga di input contiene la stringa
s (1 ≤ |s| ≤ ). È garantito che la lunghezza di s sia pari.Output
Il programma deve stampare il numero minimo di modifiche richieste per rendere valida la sequenza.
Esempi
Input | Output |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Spiegazione
- ()(( → ()() ⇒ 1 modifica
- )( → () ⇒ 2 modifiche
- ()() ⇒ nessuna modifica necessaria
- ((() → ()() ⇒ 2 modifiche
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB