Ao implementar um algoritmo que verifica se uma expressão com parênteses, colchetes e chaves está balanceada…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar algoritmos clássicos de manipulação sobre listas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Ao implementar um algoritmo que verifica se uma expressão com parênteses, colchetes e chaves está balanceada, qual estrutura de dados é mais adequada e por quê?
- A) Árvore: estrutura hierárquica não adequada para sequências lineares de parênteses e chaves.
- B) Lista: não permite acesso rápido ao último elemento, necessário para verificar correspondência.
- C) Pilha (LIFO): empilha símbolos de abertura e desempilha ao encontrar fechamento, permitindo verificar ordem e correspondência.
- D) Fila: estrutura FIFO não é correta para resolver balanceamento de parênteses.
- E) Mapa: não suporta a ordem de operações, tornando difícil verificar a hierarquia dos símbolos.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Ao verificar se uma expressão está balanceada, cada símbolo de fechamento deve corresponder ao símbolo de abertura mais recente ainda não fechado. Por exemplo, em ( [ ] ) o colchete fecha o colchete aberto mais recentemente, e depois o parêntese fecha o parêntese.
- Essa regra do 'mais recente primeiro' é exatamente o comportamento LIFO (último a entrar, primeiro a sair) de uma pilha. Ao ler um símbolo de abertura, empilha-se; ao ler um de fechamento, desempilha-se o topo e confere-se se ele é o par correspondente. Se a pilha estiver vazia no fechamento, ou sobrar algo no final, a expressão está desbalanceada.
- Portanto a alternativa C está correta, pois descreve exatamente esse mecanismo de empilhar aberturas, desempilhar nos fechamentos e verificar a correspondência e a ordem.
- Por que as outras estão erradas: A) uma árvore não é necessária, pois a sequência é linear e o problema se resolve com uma estrutura linear; B) a lista até pode ser usada, mas não oferece o acesso ao último elemento como princípio de funcionamento, e a alternativa afirma uma restrição que não é a razão central da escolha; D) a fila (FIFO) retira o elemento mais antigo, o que faria a correspondência ocorrer na ordem errada; E) um mapa associa chaves a valores e não modela a ordem de aberturas pendentes, sendo inadequado para verificar a hierarquia de aninhamento.
💡 Dica: Considere as características das estruturas de dados ao responder.
Alternativa por alternativa
Acredita que, por haver aninhamento de parênteses e chaves, a estrutura deve ser hierárquica como uma árvore, confundindo a estrutura do problema com a estrutura de dados necessária.
Supõe que a lista é inadequada porque não dá acesso rápido ao último elemento, sem perceber que uma lista pode ser usada como pilha inserindo e removendo no fim; o problema está na justificativa, não na ideia de ordem.
Por que engana: Escolher uma estrutura de dados que não permite acesso ao último elemento, como a lista, ao invés de usar a pilha que é a mais adequada para o problema.
Pilha suporta push/pop O(1); ao encontrar um fechamento verificamos topo para correspondência. Mismatch ou pilha não vazia no fim indica expressão não balanceada.
Imagina que a verificação deve seguir a ordem de chegada dos símbolos, tratando o primeiro símbolo de abertura como o primeiro a ser fechado, o que contraria o aninhamento correto.
Entende que a verificação depende de localizar pares por chave de busca, como em um mapa, e não da ordem em que as aberturas aparecem e precisam ser fechadas.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · algoritmos de verificação
Revisar as estruturas de dados e suas aplicações em algoritmos.
Escolher uma estrutura de dados que não permite acesso ao último elemento, como a lista, ao invés de usar a pilha que é a mais adequada para o problema.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Num algoritmo que converte expressões aritméticas de infixa para pós-fixa e as avalia, qual estrutura de dados é…
- Em um algoritmo que precisa permitir inserções e remoções frequentes no meio de uma sequência de comandos editáveis…
- Em um algoritmo que armazena uma sequência de comandos editáveis e de tamanho variável para executar uma ação, qual…
- Um algoritmo guarda os itens que uma família vai comprar no mercado e precisa incluir, remover e percorrer esses itens…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Em um projeto de programação, a equipe precisa guardar as tarefas a fazer em uma sequência na qual seja possível incluir…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog