Balanceamento de Parenteses

URL

https://www.thehuxley.com/problem/415

Comentários

A tarefa desse problema é verificar se em uma dada string, os parenteses e colchetes estão balanceados.

Por exemplo:

Embora você possa ficar tentado a contar a quantidade de caracteres abrindo e a quantidade de caracteres fechando e comparar pra ver se esses dois valores são iguais, você pode perceber pelos exemplos que isso não funcionaria, como em: ')(' .

A pilha é uma estrutura de dados que permite que a gente inverta as coisas, pois o primeiro a entrar é o último a sair. Por exemplo, se você inserir em uma pilha os caracteres 'A', 'B', 'C'. Quando você fizer o pop, os caracteres esperados são: 'C' , 'B', 'A'.

Vamos usar essa ideia para resolver esse problema do balanceamento. Toda vez que a gente encontrar um caracter de abertura, a gente faz um push desse caracter na pilha. Ou seja, se encontrarmos os caracteres '[' ou '(', a gente faz um push.

Toda vez que encontrarmos um caracter de fechamento, a gente faz um pop e verifica se o caracter que foi removido é o caracter de abertura equivalente.

Por exemplo, Suponha que a entrada seja:

[()]

Então, faríamos:

push('[')

push('(')

Nesse ponto, a pilha estaria assim:

O próximo caracter é um caracter de fechamento ')', então nesse caso faríamos um pop na pilha. O valor retornado pelo pop seria o caracter '('. Esse é exatamente o caracter de abertura do caracter de fechamento que acabamos de ler. Se isso acontecer, então podemos continuar a leitura do próximo caracter. Caso, isso não aconteça, significa que a entrada não está balanceada.

Se repetirmos esse procedimento até o final da entrada, e se a entrada estiver balanceada, a nossa pilha deverá estar vazia no final.