Num algoritmo que converte expressões aritméticas de infixa para pós-fixa e as avalia, qual estrutura de dados…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio de refinamentos, utilizando diversos níveis de abstração desde a especificação até a implementação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Num algoritmo que converte expressões aritméticas de infixa para pós-fixa e as avalia, qual estrutura de dados é utilizada para armazenar operadores temporariamente durante o processo?
- A) Pilha (stack).
- B) Árvore binária de busca (BST)
- C) Tabela hash (hash table)
- D) Fila (queue)
- E) Heap (fila de prioridade)
✅ Resposta correta: alternativa A
Resolução passo a passo
- Ao converter uma expressão infixa (como 3 + 4 * 2) para pós-fixa (3 4 2 * +), o algoritmo clássico de Shunting-yard, de Edsger Dijkstra, lê os tokens da esquerda para a direita e precisa guardar os operadores que ainda não podem ser colocados na saída, por causa da precedência e da associatividade.
- Para isso, usa-se uma pilha (stack), que segue a regra último a entrar, primeiro a sair. Quando chega um operador, ele é empilhado após desempilhar os operadores de maior ou igual precedência que estejam no topo, e parênteses também são tratados com a pilha.
- A mesma lógica de pilha serve para a avaliação da expressão pós-fixa: os operandos são empilhados e, ao encontrar um operador, desempilham-se os dois últimos valores, calcula-se a operação e o resultado volta para a pilha.
- Por que as outras estão erradas: a B (árvore binária de busca) organiza dados por ordenação e não serve como área temporária de operadores com acesso pelo topo; a C (tabela hash) oferece busca por chave, não ordem de empilhamento; a D (fila) remove pelo início, o que inverteria a ordem de aplicação dos operadores; a E (heap) prioriza valores por ordem, mas não preserva a sequência de chegada necessária para o algoritmo.
- Conclusão: a alternativa correta é a A, pois a pilha é a estrutura que guarda os operadores temporariamente nesse processo, coincidindo com o gabarito oficial.
💡 Dica: Pense na estrutura de dados que permite empilhar e desempilhar elementos.
Alternativa por alternativa
Pilha permite empilhar operadores e desempilhá-los na ordem inversa necessária para a conversão e avaliação (algoritmo shunting-yard e avaliação pós-fixa), preservando precedência e associatividade.
O aluno pode associar 'estrutura para guardar e organizar dados com hierarquia' a árvores e imaginar que expressões aritméticas devem ser representadas por uma árvore de busca durante a conversão.
Por que engana: Confundir a pilha com a fila, pensando que a ordem de inserção e remoção é a mesma em ambos os casos.
O aluno pode pensar que, por a conversão exigir consultar operadores e suas precedências, uma tabela hash de acesso rápido seria a estrutura adequada para armazená-los.
O aluno pode supor que operadores devem ser processados na ordem em que aparecem, como numa fila (primeiro a entrar, primeiro a sair), sem perceber que a precedência exige retirar primeiro o operador mais recente.
O aluno pode confundir a necessidade de escolher o operador de maior precedência com o uso de uma fila de prioridade, achando que o heap resolveria a ordem de aplicação.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · algoritmos de ordenação
Revisar conceitos sobre pilhas e suas aplicações em algoritmos.
Confundir a pilha com a fila, pensando que a ordem de inserção e remoção é a mesma em ambos os casos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Ao implementar um algoritmo que verifica se uma expressão com parênteses, colchetes e chaves está balanceada, qual…
- Em um algoritmo que armazena uma sequência de comandos editáveis e de tamanho variável para executar uma ação, qual…
- Em um algoritmo que precisa permitir inserções e remoções frequentes no meio de uma sequência de comandos editáveis…
- Num algoritmo que precisa inserir e remover elementos frequentemente no meio de uma sequência, qual tipo de estrutura de…
- Em um algoritmo que gerencia a fila de impressão de um laboratório de informática, qual estrutura de dados é mais…
- Analise a função recursiva que calcula o fatorial de um número. Qual é a estrutura de dados mais adequada para armazenar…
🔎 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