Corrigir a sequência de parênteses
Dada uma string s composta por parênteses de abertura e de fechamento, é permitido mudar alguns parênteses de abertura para fechamento e vice-versa. Qual é o número mínimo de operações necessárias para obter uma sequência de parênteses válida?
Entrada
A única linha da entrada contém a string s (1 ≤ |s| ≤ ). Garante-se que o comprimento de s é par.
Saída
O programa deve imprimir o menor número de modificações necessárias para que a sequência se torne válida.
Exemplos
Entrada | Saída |
|---|---|
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Explicação
()(( → ()() ⇒ 1 modificação
)( → () ⇒ 2 modificações
()() ⇒ nenhuma modificação necessária
((() → ()() ⇒ 2 modificações
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB