Neste exercício-programa, você terá que escrever um programa que lê de um arquivo polinômios e expressões envolvendo esses polinômios e calcula os polinômios resultantes de cada uma das expressões.
O método mais conhecido e eficiente para cálculo de expressões utiliza pilhas. Assim, no seu EP, você deve implementar a interface usual de pilha (veja abaixo) usando um vetor (escolha entre alocação dinâmica ou estática; o que lhe parecer mais adequado). Para facilitar o teste do seu EP, ele deve imprimir a notação posfixa de cada uma das expressões lidas do arquivo de entrada e não apenas o resultado de cada expressão.
A interface de pilha (arquivo pilha.h) que você deve implementar é a seguinte:
void inicializa (int n); /* Inicializa a ED da pilha considerando que ela comportará no máximo n elementos. */ int vazia (); /* Devolve 1 se a pilha está vazia, 0 em caso contrário. */ void empilha (elemento x); /* Empilha o elemento x na pilha. */ elemento topodapilha (); /* Devolve o elemento que se encontra no topo da pilha. */ elemento desempilha (); /* Remove o elemento do topo da pilha, devolvendo-o. */
Para que as coisas fiquem bem claras, tenha no seu EP a declaração do tipo t_pilha, que deve ser um struct, com campos correspondendo às variáveis necessárias para representar uma pilha. O tipo elemento é o tipo dos elementos armazenados na pilha.
No EP, você vai usar duas pilhas: a pilha dos operadores, usada durante a construção da notação posfixa, e a pilha de valores, usada durante o cálculo da expressão.
Utilize o seguinte para usar a pilha ora com caracteres, ora com apontadores de polinômios. Declare o tipo elemento como um union:
typedef union { char ch; apont poli; } elemento;Um union é como um struct, onde os diversos campos têm o mesmo endereço de memória, ou seja, ocupam o mesmo espaço de memória e portanto não podem ser usados simultaneamente. Especificamente, o union acima ocupa o espaço de um apont: o mais espaçoso de seus campos. Os campos de um union podem ser acessados da mesma forma que os campos de um struct.
Para utilizar a pilha com este tipo elemento, não esqueça de fazer os castings (conversões de tipo) adequadamente. Ou seja, quando empilhar um caracter, faça um casting para o tipo elemento:
empilha((elemento)ch);Analogamente, quando empilhar um apont, faça:
empilha((elemento)p);onde p é do tipo apont.
Inversamente, lembre-se que o que é devolvido pelas funções topodapilha e desempilha é neste caso um union elemento. Se você quer olhar para o valor guardado nesse union como um caracter, acesse o campo ch dele. Se você quer acessar o valor guardado nesse union como um apont, acesse o seu campo poli.
Exemplos:
while (desempilha().ch != '(')ou
apont p, q; q = desempilha().poli; p = desempilha().poli; soma(p,q);
Se você tiver dúvidas de como exatamente funciona o union, mande um e-mail para a lista de discussão com a sua dúvida ou pergunte na aula de aula.
Se você resolver usar algumas dessas funções projetadas por um colega e não as suas, guarde tais funções "emprestadas" em um arquivo separado e dê um include no seu programa, para carregar essas funções. Você deve ter o consentimento do seu colega para isso. Ao lado do include que carrega as funções do seu colega, coloque um comentário dizendo quem é o autor de tais funções (o nome do seu colega).
Especificamente, se você resolver usar funções do EP1 escritas por uma outra pessoa, no seu programa, em algum ponto no início, deve haver uma instrução
#include "extras.c"com um comentário com o nome do autor do arquivo extra.c. Algo assim, por exemplo:
/* O arquivo extras.c contém as funções escritas por Fulano de Tal e estão sendo usadas com o consentimento dele. */
O arquivo de entrada contém duas partes. A primeira parte é uma lista de polinômios enquanto que a segunda parte é uma lista de expressões envolvendo esses polinômios.
A primeira parte começa com uma linha contendo um número natural n. Este é o número de polinômios que aparecerão na lista. Em cada uma das próximas n linhas, um polinômio é dado no mesmo formato usado no EP1, exceto que ele é precedido por uma letra minúscula, que é o seu identificador. Por exemplo, o arquivo
4 p 3 1 2 -1 3 4 5 q 4 -1 0 2 2 1 3 3 4 t 1 1 1 z 2 1 1 -1 2contém a descrição de 4 polinômios:
A segunda parte consiste de uma seqüência de expressões envolvendo os identificadores que aparecem na primeira parte e os operadores '+', '-', '*', ''' (linha), que significa a derivada, e '~', que denota o menos unário (simplifica ter um símbolo diferente para este). As expressões podem ter parêntesis. Cada expressão é dada em uma linha. Comentaremos mais tarde sobre a precedência dos operadores bem como suas prioridades. Agora, veja o seguinte exemplo de segunda parte, considerando a primeira parte dada acima.
z' ~q p+q p*t (p*t)'*z p-(q+t*z)+p' t''*(~p-z) p*q*(~t)-z
A saída para tal exemplo poderia ser algo como:
expressão original: z' versão em posfixa: z' resultado: 1-2x expressão original: ~q versão em posfixa: q~ resultado: 1-2x^2-x^3-3x^4 expressão original: p+q versão em posfixa: pq+ resultado: -1+3x^2+3x^4+4x^5 expressão original: p*t versão em posfixa: pt* resultado: x^3-x^4+4x^6 expressão original: (p*t)'*z versão em posfixa: pt*'z* resultado: 3x^3-7x^4+4x^5+24x^6-24x^7 expressão original: p-(q+t*z)+p' versão em posfixa: pqtz*+-p'+ resultado: ????? (a ser completado) expressão original: t''*(~p-z) versão em posfixa: t''p~z-* resultado: 0 expressão original: p*q*(~t)-z versão em posfixa: pq*t~*z- resultado: ????? (a ser completado)
Você pode supor que a expressão é dada no arquivo sem brancos no meio. Assim, para lê-la, você pode usar o comando fscanf("%s",expr), onde expr é um vetor de caracteres.
a+b*c-d'*~eo primeiro '*' será efetuado antes do '+', o ''' e o '~' antes do segundo '*', que precederá o '-'.
O agrupamento dos operadores binários em questão é sempre da esquerda para a direita. Ou seja, na expressão
a+b-c+do primeiro '+' é efetuado, depois o '-' e finalmente o segundo '+'.
Mais especificamente, seu programa deve manter um vetor
apont polinomio[26]tal que, por exemplo, polinomio[2] é o apontador do polinômio c, ou NULL, caso não exista polinômio c. Dessa forma, pode-se acessar um polinômio de forma bem eficiente a partir de seu identificador.
/********************************************************/ /* Fulano de Tal */ /* Exercicio-Programa xx */ /* Disciplina yy Professor: Ciclano de Tal */ /********************************************************/