Parênteses balanceados com uma pilha

O problema dos parênteses

Toda expressão matemática e todo pedaço de código dependem de parênteses, colchetes e chaves bem casados. A conta 2 vezes (3 mais 4) só faz sentido com o parêntese fechado. Um código com um colchete a mais ou a menos nem roda. O problema é: dada uma sequência de abre e fecha, como um programa decide se ela está balanceada? Três coisas podem dar errado. Pode faltar um fecha, como em (( , que abre duas vezes e nunca fecha. Pode sobrar um fecha, como em ()), com um fechamento sem par. E pode haver cruzamento, como em ([)], onde os pares se atravessam na ordem errada. Um bom algoritmo precisa pegar as três.

Por que a pilha é a ferramenta perfeita aqui? Porque o balanceamento tem exatamente a estrutura aninhada que a pilha adora. Quando você abre um parêntese dentro de outro, o de dentro precisa fechar antes do de fora, na ordem inversa da abertura, que é a regra LIFO. O último que você abriu é o primeiro que deve fechar. Guardar os abre numa pilha e conferir cada fecha contra o topo reproduz essa lógica de aninhamento de forma direta. É um daqueles casamentos entre problema e estrutura que, uma vez que você enxerga, nunca mais esquece.

O algoritmo, passo a passo

O algoritmo é curto e cabe na cabeça. Percorra a expressão símbolo por símbolo. Se o símbolo é uma abertura, empilhe. Se é um fechamento, você precisa de um abre correspondente esperando no topo. Primeiro cheque se a pilha não está vazia, porque um fecha sem nada na pilha significa fechamento sobrando. Depois desempilhe e confira se o abre que saiu é do mesmo tipo do fecha atual, para pegar cruzamentos como ([)]. Ao terminar de percorrer tudo, a pilha precisa estar vazia. Se sobrou algum abre lá dentro, é porque faltou fechar. Só quando a expressão acaba com a pilha vazia é que ela está balanceada.

FUNÇÃO balanceada(expressao)
  pilha <- []
  PARA cada simbolo em expressao FAÇA
    SE simbolo é abertura ENTÃO
      empilhar(pilha, simbolo)
    SENÃO SE simbolo é fechamento ENTÃO
      SE vazia(pilha) ENTÃO
        RETORNE falso        // fecha sem par
      FIM
      abre <- desempilhar(pilha)
      SE não casa(abre, simbolo) ENTÃO
        RETORNE falso        // tipo errado, ex.: ( fecha com ]
      FIM
    FIM
  FIM
  RETORNE vazia(pilha)        // sobrou abre? entao faltou fechar
FIM

Empilha cada abertura; a cada fechamento, checa a pilha, desempilha e confere o tipo. No fim, a pilha tem que estar vazia.

As três formas de erro que a pilha pega

Repare como uma única pilha detecta os três tipos de desbalanceamento com naturalidade. Quando falta um fecha, como em ((, a pilha termina com itens sobrando, então a checagem final de pilha vazia devolve falso. Quando sobra um fecha, como em ()), em algum momento você tenta desempilhar de uma pilha vazia, e o algoritmo já retorna falso na hora. Quando há cruzamento, como em ([)], o desempilhar entrega um abre de tipo diferente do fecha atual, e a comparação de tipos acusa o erro. Um problema com três armadilhas distintas, resolvido por uma estrutura de três operações. É esse tipo de elegância que faz valer a pena aprender estruturas de dados.