Trabalho Prático - Implementação em C do Algoritmo de Avaliação de Expressões Aritméticas com TAD Pilha

Ifes Campus Serra BSI Bacharelado de Sistemas de Informação Estrutura de Dados Avaliação 4 Trabalho de Pilha TAD Pilha Obrigatório Não alterar nenhum arquivo h fornecido como material de prova Não utilize comandos em C diferentes daqueles abordados em aula Total 20 pontos Modalidade trabalho individual Entrega 04072023 até as 23h55 via ava Questão Única Adaptação de código python avaliação expressões aritméticas 20 pts O algoritmo de avaliação de expressões aritméticas recebe como entrada um texto uma string contendo uma expressão aritmética operandos operadores parênteses e produz como saída o resultado numérico da expressão A expressão de entrada está no formato infixo operadores entre os operandos Exemplo entrada 100 2 12 14 saída 100 O algoritmo fornecido aqui é uma adaptação do algorimto de Edgar Dijkstra criado originalmente para converter expressões infixas a b para expressões posfixas ab O algoritmo foi modificado para ao invés de converter a expressão de entrada para o formato posfixo calcular o valor numérico da expressão de entrada Para conseguir este efeito a fila originalmente usada por Dijkstra foi substituída por duas pilhas uma pilha de operandos e uma pilha de operadores É este algoritmo com duas pilhas que está listado a seguir Logo após o algoritmo está a listagem do programa Python que implementa o algoritmo Tarefa converta o programa Python para um programa C chamado edavalexpressaritc Sobre o programa Python Python não possui explicitamente o tipo Pilha Syack Em Pyhton um implementação frequente de pilha e aquele que usa listas Em uma implementação com listas a função append faz o papel da operação push e a função pop faz o papel da peração de desempilhamento A operação de pick geralmente é implementada apenas se verificando a última posição da lista índice 1 Sobre o programa C O programa edavalexpressaritc deve fazer o uso do tad pilha construído em aula replit Todas as funções de pilha mapeadas do programa Python devem ser adaptadas para a interface do tad pilha Nenhum arquivo h fornecido para a prova deve ser alterado Crie expressões de teste para avaliar a sua implementação Ex 100 2 12 Algortimo para entender o processo de Dijkstra modificado 1 Embora ainda haja tokens a serem lidos 11 Obtenha o próximo token 12 Se o token for 121 Um número coloqueo na pilha de valores 122 Uma variável obtenha seu valor e coloqueo na pilha de valores 123 Um parêntese esquerdo coloqueo na pilha de operadores 124 Um parêntese direito 1 Enquanto o elemento no topo da pilha de operadores não seja um parêntese esquerdo 1 Retire o operador da pilha de operadores 2 Abra a pilha de valores duas vezes obtendo dois operandos 3 Aplique o operador aos operandos na ordem correta 4 Armazene o resultado para a pilha de valores 2 Retire o parêntese esquerdo da pilha de operadores e descarteo 125 Seja um operador chameo de Op 1 Enquanto a pilha de operadores não estiver vazia e o elemento no topo da pilha de operadores tem precedência igual ou maior que Op 1 Retire o operador da pilha de operadores 2 Abra a pilha de valores duas vezes obtendo dois operandos 3 Aplique o operador aos operandos na ordem correta 4 Armazene o resultado para a pilha de valores 2 Armazene Op na pilha de operadores 2 Enquanto a pilha de operadores não estiver vazia 1 Retire o operador da pilha de operadores 2 Abra a pilha de valores duas vezes obtendo dois operandos 3 Aplique o operador aos operandos na ordem correta 4 Armazene o resultado para a pilha de valores 3 Neste ponto a pilha de operadores deve estar vazia e a pilha de valores deve ter apenas um valor nela que é o resultado final Programa Python na próxima página Programa Python com o algoritmo de Dijkstra modificado para avaliação de expressões aritméticas Python3 este programa avalia uma dada expressão aritmética onde operadores operandos e parênteses estão separados entre si por espaços Function to find precedence of operators def precedenceop if op or op return 1 if op or op return 2 return 0 Function to perform arithmetic operations def applyOpa b op if op return a b if op return a b if op return a b if op return a b Function that returns value of expression after evaluation def evaluatetokens stack to store integer values values stack to store operators ops i 0 while i lentokens Current token is a whitespace skip it if tokensi i 1 continue Current token is an opening brace push it to ops elif tokensi opsappendtokensi Current token is a number push it to stack for numbers elif tokensiisdigit val 0 There may be more than one digits in the number while i lentokens and tokensiisdigit val val 10 inttokensi i 1 valuesappendval right now the i points to the character next to the digit since the for loop also increases the i we would skip one token position we need to decrease the value of i by 1 to correct the offset i1 Closing brace encountered solve entire brace elif tokensi while lenops 0 and ops1 val2 valuespop val1 valuespop op opspop valuesappendapplyOpval1 val2 op pop opening brace opspop Current token is an operator else While top of ops has same or greater precedence to current token which is an operator Apply operator on top of ops to top two elements in values stack while lenops 0 and precedenceops1 precedencetokensi val2 valuespop val1 valuespop op opspop valuesappendapplyOpval1 val2 op Push current token to ops opsappendtokensi i 1 Entire expression has been parsed at this point apply remaining ops to remaining values while lenops 0 val2 valuespop val1 valuespop op opspop valuesappendapplyOpval1 val2 op Top of values contains result return it return values1 Código de teste if name main printevaluate10 2 6 printevaluate100 2 12 printevaluate100 2 12 printevaluate100 2 12 14 This code is contributed by Rituraj Jain Entrega Crie um arquivo chamado trabpilhafilazip contendo os seguintes arquivos compactados edavalexpressaritc tadpilhah tadpilhac tadlistah tadlistac Compactações em formato rar não serão corrigidas Entregue o arquivo compactado na tarefa do ava aberta para a avaliação do tad pilha Aviso importante Somente serão corrigidas as soluções entregues via tarefa do ava associada à avaliação Soluções não entregues ou entregues via outros mecanismos receberão a nota zero Caso não consiga fazer a entrega da tarefa devido a questões técnicas como falta de conexão com internet ou servidor ava fora do ar registre a causa do impedimento e procure o Professor no dia seguinte a entrega Compareça levando o arquivo trabpilhafilazip e providencie o devido envio para a tarefa do ava Não seguir o procedimento do parágrafo anterior implicará em nota zero para a avaliação Bons estudos