Segundo Exercício-Programa

Entrega: 6 de maio

Este EP pode ser feito em dupla.

Cálculo de Expressões com Polinômios Esparsos

Esse EP é uma extensão do EP anterior. Se você não fez o EP anterior ou seu EP tinha muitos problemas, você poderá usar rotinas do EP de um colega seu, se quiser. Falaremos mais sobre isso abaixo.

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 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);

Idem quando empilhar um apont:

  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 != '(')

  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.

Polinômios

Os polinômios devem ser armazenados em listas ligadas, exatamente no formato usado no EP1. As funções implementadas no EP1 que você vai precisar neste EP são as seguintes: le, imprime, copia, soma, subtrai, multiplica e deriva, além das funções de manipulação da lista livre. Além destas, você deve implementar uma função nega, que multiplica o polinômio por -1, ou seja, multiplica cada coeficiente dos monômios do polinômio por -1.

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. No arquivo onde estão as funções do seu colega, coloque um comentário dizendo quem são os autores de tais funções (o nome do seu colega ou da dupla, se for o caso).

Mais especificamente, se você resolver usar funções do EP1 escritas por outras pessoas, no seu programa, em algum ponto no início, deve haver uma instrução

#include "extras.c"

e no arquivo extra.c haveria no início um comentário do tipo

/* Essas funções foram escritas originalmente pelo Fulano de Tal e
   pela Beltrana de Tal e estão sendo usadas com o consentimento deles. */

seguido das funções "emprestadas". Comente no arquivo qualquer modificação que você tenha feito nas funções originais.

Arquivo de entrada

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 2

contém a descrição de 4 polinômios:
p = x²-x³+4x⁵
q = -1+2x²+x³+3x⁴
t = x
z = x-x²

Utilize portanto uma versão levemente modificada da função le do EP1 para fazer a leitura desta parte. Após a leitura de cada polinômio do arquivo de entrada, imprima-o, usando a função imprime do EP1. Não se esqueça de imprimir o identificador do polinômio também! Aliás, onde você vai guardar tal identificador?

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:          -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.

Prioridades e precedências

A precedência dos operadores determina qual operador "precede" o outro, ou seja, qual deve ser efetuado primeiro. Os operadores usados nesse EP em ordem de precedência são: ''', '~', '*' e, empatados (ou seja, com a mesma precedência), '+' e '-'. Por exemplo, na expressão

a+b*c-d'*~e

o 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+d

o primeiro '+' é efetuado, depois o '-' e finalmente o segundo '+'.

Identificadores

Ao ler a segunda parte, você vai ter que associar os polinômios montados na primeira parte aos identificadores que aparecem nas expressões. Para tanto, utilize um vetor com 26 posições (uma para cada letra minúscula) que contém em cada posição NULL, caso o identificador não tenha aparecido, ou um apontador para o polinômio.

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.

Organização do EP

O seu programa deve conter, além das funções previamente mencionadas, as duas seguintes funções:

void converte (char original[], char posfixa[]);
Recebe uma string, original, que contem uma expressão, como as dadas no arquivo de entrada, e devolve na string posfixa a expressão posfixa correspondente.
apont calcula (char posfixa[], apont polinomio[]);
Recebe uma string posfixa e o vetor polinomio, mencionado acima, e devolve o apontador para um polinômio que contém o resultado da expressão em posfixa.

Avisos

Se você decidir fazer o programa em dupla, não deixe o seu parceiro fazer tudo ou quase tudo sozinho! Divida o trabalho para que você não perca a chance de aprender os tópicos em questão.
Sugestão de divisão de trabalho: um membro da dupla pode escrever a função converte e as modificações das funções do EP1, enquanto o outro escreve o programa principal e a função calcula.
Seu programa deve ser o mais eficiente possível. Se você implementar algoritmos desnecessariamente ineficientes, você poderá perder pontos.
Seu programa deve estar bem indentado, bem documentado e organizado. Isso será fortemente levado em conta na sua nota.
Discuta os seus problemas e suas idéias com o seu parceiro. Essa é a razão desse EP poder ser feito em dupla: para você ter uma oportunidade de aprender discutindo com um colega. E para ser mais divertido também!!
Não serão aceitos exercícios-programa atrasados, portanto comece cedo a fazer o seu EP!

Todos os exercícios-programas devem ter um cabeçalho do seguinte tipo:

    /********************************************************/
    /* Fulano de Tal e Beltrano de Tal                      */
    /* Exercicio-Programa xx                                */
    /* Disciplina yy            Professor:  Ciclano de Tal  */
    /********************************************************/

Exercícios com erros de sintaxe (ou seja, erros de compilação) receberão nota ZERO.
A entrega do EP será eletrônica. Você receberá mais informações sobre isso na lista de discussão.
Guarde com você atê o final do semestre, em seus disquetes, os arquivos de seus programas, pois eles podem ser solicitados pelo professor caso surja alguma dúvida. Guarde também as listagens que lhe serão devolvidas, nas quais está marcada a nota que você recebeu.
EPs copiados, exceto pelas partes permitidas pelo enunciado (desde que com os devidos créditos), receberão nota zero: fonte e cópia. Assim, não copie o EP de outra pessoa nem empreste seu EP ou parte dele para ninguém. Seja cuidadoso para que alguém não copie seu EP sem a sua permissão.

Last modified: Fri Apr 26 11:55:14 EST 2002