[PILHA] Utilizando pilha para resolver o problema de balanceamento de parênteses

Olá, pessoal! estou aqui para compartilhar uma das aplicações da estrutura de dados pilha, que a tem a propriedade FILO (First In Last Out) - o primeiro a entrar é o último a sair.

O problema em questão é o balanceamento de parênteses.

A ideia para resolver o problema é bastante simples, vamos formar ‘parzinhos’ de ( e ). Então para todo ( deve existir o seu respectivo ). E quando aparece um ) o seu par é o imediato ( que ainda não possui par.

Observe a figura que mostra o pareamento identificado por cores

parenteses

Para que, de fato criemos o algoritmo, vamos entender a ideia geral de implementção.
A Pilha tem duas operações básicas

  1. Inserir um elemento no final da estrutura
  2. Remover o último elemento adicionado

Para a operação do tipo 1, vamos executá-la sempre que encontrarmos um (;
Para a operação do tipo 2, vamos executá-la sempre que encontrarmos um ).

Observe que nunca empilharemos um )

Agora temos 3 cenários possíveis:

  1. Tentar desempilhar um elemento em uma pilha vazia;
  2. Terminar de avaliar a expressão e ainda conter elementos na pilha;
  3. Terminar de avaliar a expressão e a pilha está vazia.

O cenário 1 nos diz que estamos fechando um parêntese que nunca fora aberto;
O cenário 2 nos diz que temos algum parêntese aberto excedente;
O cenário 3 nos diz que para todo ‘(’ existe um ‘)’, logo, temos uma expressão devidamente balanceada.

O algoritmo para a solução desse problema é apresentado a seguir:

/* nome do arquivo: balanceado.js */
/*
    a função "balanceado" espera receber uma string contendo apenas '(' e ')'
    retorna true se a string (expressão) é balanceada
    retorna false caso contrário
*/

function balanceado(exp) {

    let pilha = [] // vai representar a estrutura de dados

    for (let i=0; i<exp.length; ++i) {

        if (exp[i] === '(') {
            // vamos inserir na pilha
            pilha.push(exp[i]) // insere o elemento no final
        } else {
            // aqui vamos ter que desempilhar, porque encontramos um ')'
            // pois para todo ')' deve existir um '('

            // no entanto, para fechar um parentese, é necessário que exista um abrindo
            if (pilha.length === 0) // se não existir um '(' na pilha
                return false // a expressão está desbalanceada

            // conseguimos formar um par '()'
            pilha.pop() // removendo o último que entrou
        }
    }

    // nesse ponto garantimos que não existe um ')' a mais que o devido
    // mas ainda pode existir '(' sobrando
    if (pilha.length !== 0) // existe mais '(' que ')'
        return false

    // aqui é garantido que temos uma expressão balanceada
    // pois para todo '(' existe um ')' correspondente
    return true
}

module.exports = balanceado

É fácil enxergar os cenários sendo tratados no algoritmo?
Temos alguns casos de testes para avaliar o algoritmo

const assert = require('assert')
const balanceado = require('./balanceado')

assert.equal(balanceado(''), true)
assert.equal(balanceado('('), false)
assert.equal(balanceado(')'), false)
assert.equal(balanceado('()'), true)
assert.equal(balanceado(')('), false)
assert.equal(balanceado('()('), false)
assert.equal(balanceado(')))((('), false)
assert.equal(balanceado('()()()()()()()()'), true)
assert.equal(balanceado('()()()()()()()()((())())'), true)
assert.equal(balanceado('(((((((((((())))))))))))'), true)

Um problema similar a esse pode ser encontrado aqui:

Espero que tenham gostado.

2 Likes

Esse eh top hein. Valeu pela dica!

2 Likes