Este artigo explora um método para determinar se uma string contendo apenas parênteses, chaves e colchetes é "válida". Uma string é considerada válida se:

• Cada parêntese de abertura tem um parêntese de fechamento correspondente do mesmo tipo.
• Os parênteses de abertura são fechados na ordem correta.
• Não há parênteses de fechamento sem um parêntese de abertura correspondente.

Considere os seguintes exmeplos:

• Entrada: s = "()[]{}"
  Saída: true
• Entrada: s = "(]"
  Saída: false

O problema pode ser abordado utilizando uma estrtuura de dados de pilha. Ao iterar pela string:

• Se um caractere de abertura for encontrado ('(', '{', '['), seu correspondente caractere de fechamento (')', '}', ']') é empilhado.
• Se um caractere de fechamento for encontrado:
  • Primeiro, verifica-se se a pilha está vazia. Se estiver, significa que não há um parêntese de abertura correspondente, e a string é inválida.
  • Em seguida, compara-se o caractere de fechamento atual com o elemento no topo da pilha. Se eles não corresponderem, a string é inválida.
  • Se corresponderem, o elemento do topo da pilha é desempilhado.

Após a iteração completa da string, se a pilha estiver vazia, todos os parênteses foram corretamente correspondidos e fechados, indicando que a string é válida. Caso contrário, a string é inválida.

Uma otimização inicial é verificar se o comprimento da string é ímpar. Se to, a string não pode ser válida, pois um parêntese deve ter um correspondente.

Implementação em Java:

import java.util.Stack;

class ValidadorParenteses {
    public boolean ehValido(String s) {
        // Se o comprimento da string for ímpar, não pode ser válido.
        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<character> pilhaDeFechamentos = new Stack<>();
        char[] caracteres = s.toCharArray();

        for (char caractereAtual : caracteres) {
            if (caractereAtual == '(') {
                pilhaDeFechamentos.push(')');
            } else if (caractereAtual == '{') {
                pilhaDeFechamentos.push('}');
            } else if (caractereAtual == '[') {
                pilhaDeFechamentos.push(']');
            } else {
                // Se for um caractere de fechamento, verifica a pilha.
                if (pilhaDeFechamentos.isEmpty() || pilhaDeFechamentos.peek() != caractereAtual) {
                    return false; // Pilha vazia ou topo não corresponde.
                }
                pilhaDeFechamentos.pop(); // Correspondência encontrada, remove da pilha.
            }
        }

        // Se a pilha estiver vazia no final, todos os parênteses foram validados.
        return pilhaDeFechamentos.isEmpty();
    }
}
</character>

Uma alternativa ligeiramente mais verbosa para a lógica de verificação de caracteres de fechamento é apresentada abaixo:

import java.util.Stack;

class ValidadorParentesesAlternativo {
    public boolean ehValido(String s) {
        // Se o comprimento da string for ímpar, não pode ser válido.
        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<character> pilhaDeFechamentos = new Stack<>();
        char[] caracteres = s.toCharArray();

        for (char caractereAtual : caracteres) {
            if (caractereAtual == '(') {
                pilhaDeFechamentos.push(')');
            } else if (caractereAtual == '{') {
                pilhaDeFechamentos.push('}');
            } else if (caractereAtual == '[') {
                pilhaDeFechamentos.push(']');
            } else if (pilhaDeFechamentos.isEmpty()) {
                return false; // Caractere de fechamento sem um par correspondente.
            } else {
                // Verifica se o caractere de fechamento atual corresponde ao topo da pilha.
                if (pilhaDeFechamentos.peek() == caractereAtual) {
                    pilhaDeFechamentos.pop(); // Correspondência encontrada, remove da pilha.
                } else {
                    return false; // Não há correspondência.
                }
            }
        }

        // Se a pilha estiver vazia no final, todos os parênteses foram validados.
        return pilhaDeFechamentos.isEmpty();
    }
}
</character>