Atividade Avaliativa 2 - Implementacao de Pilha Estatica para Analise de Expressoes

INSTITUTO FEDERAL FLUMINENSE IFF Campus Itaperuna Prof Leandro Fernandes dos Santos leandrofsantosiffedubr Disciplina Estruturas de Dados Atividade Avaliativa 2 Módulo 2 Turma Sistemas de Informação 3º Período Objetivo Esta atividade tem como objetivo consolidar o conceito de pilha implementada de maneira estática e suas principais operações Observações e regras de entrega Deverá ser realizada de forma individual Terá o valor de 4 pontos na composição da nota na A2 A solução deverá ser enviada por meio da plataforma runcodes até as 23h59min do dia 12032023 Pontos importantes a serem seguidos Conformidade com os requisitos aqui apresentados Uso dos conceitos de modularização Códigos bem estruturados e bem indentados Caso seja detectada a ocorrência de plágio será atribuída nota zero a todos os envolvidos Submissões que apresentarem erros de compilação ou falhas de segmentação no runcodes NÃO serão corrigidas O não atendimento dos requisitos especificados neste documento acarretará em perda de pontos Instituto Federal FluminenseIFF Campus Itaperuna Especificacao Este exercıcio tratase da implementacao de uma pilha para a solucao de um problema que consiste basicamente na analise da validade de uma expressao quanto ao aninhamento de 3 delimitadores de escopo parˆenteses chaves ou colchetes Desta forma um finalizador de escopo deve ser do mesmo tipo de seu iniciador Sendo assim expressoes do tipo A B A B A B sao invalidas Assim tornase necessario rastrear os escopos abertos e seus respectivos tipos Estas informacoes sao importantes pois toda vez que um finalizador de escopo for encontrado entao precisamos conhecer o sımbolo com o qual o escopo foi aberto para assegurar que ele seja corretamente fechado Um pilha pode ser utilizada para rastrear os tipos de escopos encontrados Sempre que um iniciador de escopo ou for encontrado ele sera empilhado push Sempre que um finalizador de escopo for encontrado entao a pilha sera analisada Se a pilha estiver vazia entao o finalizador de escopo nao tera um inicializador correspondente e a string sera con sequentemente invalida De outro modo se a pilha nao estiver vazia desempilharemos pop e verificaremos se o item desempilhado corresponde ao inicializador de escopo relacionado ao finalizador encontrado Se ocorrer uma coincidˆencia entao o processo de analise continua caso contrario a string sera invalida Quando o final da string for alcancado a pilha devera estar vazia caso contrario existira um ou mais escopos abertos sem terem sido fechados e a string tambem sera invalida Abaixo seguem algumas imagens sobre o comportamento da pilha durante a analise da ex pressao x y a b c d e 2 Instituto Federal FluminenseIFF Campus Itaperuna Em seguida encontrase o pseudoalgoritmo referente a funcao expression analyze responsavel pela analise das expressoes Algoritmo 1 expression analyzes expr Entrada Pilha vazia s e Vetor com expressao expr a ser analisada Saıda 1 caso expr seja valida 0 caso contrario 1 i 0 2 valid 1 3 symbol expr0 4 popped 0 5 enquanto o final da string nao for atingido 6 enquanto symbol 0 faca 7 se symbol symbol symbol entao 8 pushs symbol empilha 9 se symbol symbol symbol entao 10 se emptys entao 11 valid 0 12 senao 13 popped pops desempilha 14 se popped nao corresponde ao iniciador de symbol entao 15 valid 0 16 i i 1 17 symbol expri 18 se not emptys entao 19 valid 0 20 retorna valid 3 Instituto Federal FluminenseIFF Campus Itaperuna A solucao deste problema requer o uso de uma pilha pois o ultimo escopo a ser aberto dever ser o primeiro a ser fechado Isto e simulado por uma pilha na qual o ultimo elemento a entrar e o primeiro a sair Last In First Out LIFO Para a realizacao deste trabalho vocˆe devera construir um programa em C chamado expres sion analyzer que contera uma pilha internamente para analisar expressoes passadas para a funcao expression analyze acima descrita Os requisitos a serem seguidos sao Sua pilha devera ser implementada usando listas encadeadas como visto em aula Devera existir um tipo estruturado struct chamado Node contendo os seguintes campos symbol Variavel do tipo caractere que armazenara um sımbolo delimitador de es copo next Ponteiro para o proximo elemento da pilha Devera tambem existir um tipo estruturado com o nome Stack contendo o seguinte campo top Ponteiro para estruturas do tipo Node referenciando elementos da pilha A operacao de empilhar devera ser implementada usando o seguinte prototipo void pushStack s char e onde s representa a pilha e e o elemento a ser empi lhado A operacao de desempilhar devera ser implementada usando o seguinte prototipo char popStack s onde s representa a pilha A funcao devera retornar o elemento que foi desempilhado Devera existir uma operacao para verificacao de pilha vazia Esta funcao devera seguir o prototipo short int isEmptystack s onde s representa a pilha Sua funcao devera retornar 1 caso a pilha esteja vazia e 0 caso contrario Lembrese que neste contexto uma pilha vazia significa top NULL A funcao expression analyze do Algoritmo 1 devera possuir o seguinte prototipo short int expression analyzeStack s char expr onde s representa a pilha e expr a expressao a ser analisada Esta funcao devera retornar 1 caso a expressao seja valida e 0 caso contrario Deverao existir funcoes para esvaziar a pilha e liberala como vistas em aula pois em caso de expressao invalida ainda podem restar elementos na pilha Quando o programa for executado este devera solicitar a expressao ao usuario por meio de um simples scanf e devera responder com a mensagem Validaem caso de validade da expressao ou Invalidacaso contrario Abaixo seguem alguns exemplos de como o seu programa devera se comportar expression analyzer a b c d e Valida 4 Instituto Federal FluminenseIFF Campus Itaperuna expression analyzer x3zyˆ257qabˆ3 Valida expression analyzer ab c Invalida expression analyzer ab c Invalida expression analyzer 1 Valida Comece a tentar resolver o exercıcio o quanto antes enquanto os assuntos tratados estao frescos na memoria e o prazo para terminalo esta tao longe quanto jamais podera estar Bom Trabalho 5