Descubra o Algoritmo por Trás das Pontuações Perfeitas: Será que suas Expressões Estão Bem Formadas?

Você já parou para pensar como um computador poderia analisar se uma expressão matemática ou um conjunto de parênteses, colchetes ou chaves está bem formado? Bem, hoje vamos entrar nesse universo fascinante com um algoritmo simples e eficaz, frequentemente utilizado em entrevistas de emprego, como as do Facebook, para verificar a formação correta de expressões.

Imaginemos a expressão: {[()]}. Aqui, cada símbolo de abertura tem um símbolo de fechamento correspondente. O nosso desafio? Criar um algoritmo que valide se a formação de expressões é correta.

Passo a Passo: Entendendo o Algoritmo

Vamos desconstruir o algoritmo e entender cada parte dele. Você não precisa ser um programador experiente para acompanhar – prometo usar palavras simples e direta!

1. Identificando os Símbolos Válidos

O primeiro passo é saber quais caracteres vamos considerar na nossa análise.

const accepted = ['{', '[', '(', '}', ']', ')'];

Este código define quais são os símbolos que o algoritmo irá analisar. Tudo que não for um desses caracteres será ignorado, já que não queremos saber de letras ou números aqui.

2. Filtrando a Lista

Uma vez definido quais caracteres são aceitos, precisamos criar uma lista somente com esses símbolos da nossa expressão.

const list = text.split('').filter((item) => accepted.includes(item));

Aqui, o texto é separado em sua forma individual de caracteres, e então usamos um filtro para deixar só aqueles que são relevantes para nós.

3. Checando a Correspondência

Agora, precisamos verificar se os símbolos estão corretamente pareados.

if (list.length % 2 !== 0) return false;

Se a lista tiver um número ímpar de elementos, já podemos parar por aqui: impossível estarem todos corretamente pareados!

4. Criando os Pares de Símbolos

Vamos definir como os pares de abertura e fechamento devem corresponder entre si.

let exists = [['{', '}'], ['[', ']'], ['(', ')']];
const opensSequence = [];
const closedsSequence = [];

Criamos exists para definir quais são nossos pares válidos. Em seguida, dois arrays vazios vão nos ajudar a identificar a sequência de abertura e fechamento.

5. Lógica de Verificação

Aqui é onde acontece a magia do algoritmo, dividindo a lista em duas metades para verificar.

for (let i = 0; i < list.length; i++) {
    if ((i + 1) * 2 <= list.length) {
       let position = -1;
       exists.forEach((element, index) => {
           if (list[i] === element[0]) {
               position = index;
               opensSequence.push(index);
           }
       });
       if (position == -1) return false;
   } else {
       let position = -1;
       exists.forEach((element, index) => {
           if (list[i] === element[1]) {
               position = index;
               closedsSequence.push(index);
           }
       });
       if (position == -1) return false;
    }
}

– A Primeira Metade:

Na primeira metade da nossa lista de caracteres, procuramos por símbolos de abertura. Se encontrado, armazenamos a posição do seu par correspondente no array opensSequence.

– A Segunda Metade:

Na segunda metade, verificamos os símbolos de fechamento e guardamos suas posições no array closedsSequence. Se não encontrarmos, retornamos falso.

6. Verificar a Correspondência

Por fim, precisamos comparar se os pares de índices nos dois arrays (opensSequence e closedsSequence) correspondem perfeitamente.

closedsSequence.reverse();
return opensSequence.every((value, index) => value === closedsSequence[index]);

Aqui, closedsSequence.reverse() é necessário para inverter a ordem dos fechamentos e assim cada abertura se alinhar ao fechamento correspondente.

Colocando Tudo Junto

Todo o código, já explicado, para você testar:

const isWellFormat = (text) => {
const accepted = ['{', '[', '(', '}', ']', ')'];
const list = text.split('').filter((item) => accepted.includes(item));
if (list.length % 2 !== 0) return false;
    let exists = [['{', '}'], ['[', ']'], ['(', ')']];
    const opensSequence = [];
    const closedsSequence = [];
    for (let i = 0; i < list.length; i++) {
        if ((i + 1) * 2 <= list.length) {
            let position = -1;
            exists.forEach((element, index) => {
                if (list[i] === element[0]) {
                    position = index;
                    opensSequence.push(index);
                }
            });
            if (position == -1) return false;
        } else {
            let position = -1;
            exists.forEach((element, index) => {
                if (list[i] === element[1]) {
                    position = index;
                    closedsSequence.push(index);
                }
            });
            if (position == -1) return false;
        }
    }
    closedsSequence.reverse();
    return opensSequence.every((value, index) => value === closedsSequence[index]);
};

console.log(isWellFormat('[()]') === true); // true
console.log(isWellFormat('[(}]') === false); // false
console.log(isWellFormat('[((]') === false); // false
console.log(isWellFormat('[({(]))}') === false); // false
console.log(isWellFormat('[({(A))}') === false); // false
console.log(isWellFormat('[({A})]') === true); // true

Conclusão

Agora você já conhece um dos algoritmos mais famosos em entrevistas técnicas! Esse algoritmo permite que você teste se uma expressão é bem-formada. Independentemente do seu nível de experiência, você pode agora entender como um problema aparentemente complexo pode ser resolvido com um conjunto de passos simples e bem pensados.\n\nUse este conhecimento para se destacar em entrevistas e desafios de lógica, impressionando todos ao mostrar que a complexidade muitas vezes é facilmente cavalgável quando dividida em pequenas partes!