Segundo Exercício-Programa

Calculadora de polinômios esparsos

Entrega: 3 de outubro

O objetivo deste exercício-programa é implementar uma calculadora que manipula polinômios esparsos. Polinômios esparsos são polinômios usualmente de grau alto, mas com poucos termos não nulos. Tais polinômios podem ser armazenados eficientemente em uma lista ligada que contém, em cada célula, os dados de um dos termos não nulos do polinômio.

Exemplo: O polinômio p(x)=-x⁵³+2x³⁷+5x¹¹-7 poderia ser armazenado em uma lista de acordo com a seguinte figura:

onde ini é o apontador para o início da lista, o primeiro campo de cada célula guarda o coeficiente de um termo do polinômio, o segundo campo guarda o expoente do termo, e o terceiro campo é o usual apontador para a próxima célula da lista. Note a ausência de termos cujo coeficiente é nulo.

Na lista ligada acima, não usamos cabeça de lista, mas você pode optar por usar, se isso tornar a sua implementação melhor. Observe que, na lista acima, as células aparecem em ordem decrescente de expoente. Esta também é uma opção do programador. As células poderiam aparecer em uma ordem arbitrária, ou em ordem crescente de expoente, ou numa outra ordem. A escolha é do programador, ou seja, é sua. Escolha a ordem que tornar a sua implementação a melhor possível. O único ponto que você não pode abrir mão na representação de polinômios esparsos é que a lista não deve conter termos com coeficiente nulo.

Para fazer a escolha do tipo de lista ligada que você vai usar no seu programa, é essencial pensar nas operações que você vai implementar sobre estas listas. Vamos então a elas.

Operações da calculadora

As seguintes operações deve estar implementadas na calculadora: soma, subtração, multiplicação, divisão e resto. Especificamente, você deve escrever uma biblioteca que implementa o tipo abstrato de dados Polinômio. A interface da sua biblioteca deve ser o arquivo polinomio.h, contendo o seguinte:

typedef struct termo *polinomio;

polinomio crie_monomio(double, int);

void libere(polinomio);

polinomio leia_polinomio();

void imprima(polinomio);

polinomio some(polinomio, polinomio);

polinomio subtraia(polinomio, polinomio);

polinomio negue(polinomio);

polinomio multiplique(polinomio, polinomio);

polinomio quociente(polinomio, polinomio);

polinomio resto(polinomio, polinomio);

Note que o arquivo polinomio.h especifica o que se pode fazer com um polinômio (isto é, as operações sobre polinômios), mas não informa como um polinômio é implementado. O tipo polinomio é definido como um apontador para uma estrutura cuja definição não é parte da interface da biblioteca. A definição da estrutura struct termo não aparece no arquivo polinomio.h.

Abaixo descrevemos o que deve fazer cada uma das funções da biblioteca:

```
polinomio crie_monomio(double coef, int exp);
```
Cria um novo monômio (um polinômio com um só termo) cujo coeficiente é coef e o expoente é exp. A função devolve o monômio criado. Caso o parâmetro coef seja igual a zero, esta função cria um polinômio nulo (um polinômio que não possui nenhum termo com coeficiente não nulo) e devolve o polinômio nulo criado.
```
void libere(polinomio p);
```
Libera a memória ocupada pelo polinômio p.
```
polinomio leia_polinomio();
```
Lê um inteiro nÃŁo negativo n e uma sequência de n pares de números, cada par consistindo de um real (representando um coeficiente) e um inteiro não negativo (representando um expoente). Devolve um novo polinômio com os n termos dados pelos pares.
```
void imprima(polinomio p);
```
Recebe um polinômio p e o imprime.
```
polinomio some(polinomio p, polinomio q);
```
Recebe dois polinômios, p e q, e devolve como valor da função a soma de p e q.
```
polinomio subtraia(polinomio p, polinomio q);
```
Recebe dois polinômios, p e q, e devolve como valor da função a diferença entre p e q, ou seja, p-q.
```
polinomio negue(polinomio p);
```
Recebe um polinômio p, e devolve como valor da função a o polinômio -p.
```
polinomio multiplique(polinomio p, polinomio q);
```
Recebe dois polinômios, p e q, e devolve como valor da função o produto de p e q.
```
polinomio quociente(polinomio p, polinomio q);
```
Recebe dois polinômios, p e q, e devolve como valor da função o quociente da divisão de p e q. Veja um exemplo mais adiante.
```
polinomio resto(polinomio p, polinomio q);
```
Recebe dois polinômios, p e q, e devolve como valor da função o resto da divisão de p e q. Veja um exemplo mais adiante.

Nenhuma das funções acima modifica algum polinômio recebido como parâmetro. Todos os polinômios devolvidos por essas funções são alocados dinamicamente e devem ser liberados (mediante chamadas à função libera) quando não tiverem mais utilidade para o cliente da biblioteca. Por exemplo: se uma variável u referenciar um polinomio, é um erro deixar que u saia de escopo sem antes executar libera(u). Também é um erro atribuir outro polinomio a u sem antes executar libera(u). Considere o seguinte exemplo, que imprime a soma e o produto de dois polinômios dados:

    polinomio p, q, r;
    p = ...;              /* inicializa p com algum polinômio */
    q = ...;              /* inicializa q com outro polinômio */
    u = soma(p, q);       /* inicializa v com o polinômio soma p+q */
    imprime(u);           /* imprime o polinômio soma */
    libera(u);            /* libera o polinômio soma */
    u = multiplica(p, q); /* atribui a v o polinômio produto p*q */
    imprime(u, stdout);   /* imprime o polinômio produto */

Exemplo: Considere os polinômios p(x)=-8x⁵+2x³+5x²-7 e q(x)=2x³-x²+2. O quociente de p(x) por q(x) é o polinômio t(x)=-4x²-2x, enquanto que o resto é o polinômio r(x)=13x²+4x-7. De fato, o polinômio r(x) tem grau estritamente menor que o polinômio q(x) e você pode verificar que p(x) = q(x)*t(x) + r(x).

A implementação da biblioteca (o arquivo polinomio.c) deve incluir as seguintes declarações:

#include 
#include 
...
#include "polinomio.h"

struct termo {
  double coef;
  int exp;
  struct termo *prox;
};

A estrutura struct termo é usada para as células dos polinômios. Em outras palavras, cada polinômio é uma lista ligada de struct termo. Note, entretanto, que os programas que forem usar a sua biblioteca de polinômios (os clientes da biblioteca) não precisam saber nada disso. Esses programas não precisam conhecer a estrutura struct termo, nem saber que internamente a biblioteca implementa polinômios como listas ligadas com ou sem cabeça. Para escrever um cliente é suficiente conhecer a interface da biblioteca (o arquivo polinomio.h) e saber o que fazem as funções dessa interface.

Requisitos adicionais sobre a implementação da biblioteca

A implementação da sua biblioteca deve estar armazenada no arquivo polinomio.c.
Sua implementação das funções some e subtraia deve ser eficiente: os polinômios de entrada devem ser percorridos apenas uma vez.
Sua implementação das funções libere, imprime e negue deve ser eficiente: o polinômio de entrada deve ser percorrido apenas uma vez.
Sua implementação das funções multiplique, quociente e resto também devem ser tão eficientes quanto possível.
A implementação da biblioteca deve obrigatoriamente usar uma lista livre. Funções ou variáveis auxiliares que você criar dentro da sua biblioteca, por exemplo, a variável livre e as funções de manipulação da lista livre, devem ser declaradas como estáticas (static), de modo a serem acessíveis apenas dentro da sua biblioteca.
Sua biblioteca deve poder ser compilada separadamente do seu arquivo que contém o programa cliente da biblioteca.

Se você implementar a sua biblioteca corretamente e um colega seu implementar o programa cliente corretamente, o cliente do seu colega poderá usar a sua biblioteca.

Programa cliente: a calculadora

Além da implementação da biblioteca, você deverá entregar um programa que usará a biblioteca, ou seja, um programa cliente, que usará as funções da biblioteca polinomio.h.

O programa cliente deve implementar uma calculadora que mantém um conjunto de 23 variáveis identificadas pelas letras minúsculas de 'a' a 'w'. Os valores dessas variáveis são polinômios. O usuário da calculadora pode efetuar operações envolvendo essas variáveis.

Este é um exemplo de uso da calculadora:

a?
a(x) = 0
p?
p(x) = 0
p: 3 4 5 -1 3 1 2
p(x) = 4x^5 - x^3 + x^2
q: 4 2 2 3 4 1 3 -1 0
q(x) = 3x^4 + x^3 + 2x^2 - 1
r=p+q
r(x) = 4x^5 + 3x^4 + 3x^2 - 1
s=p*q
s(x) = 12x^9 + 4x^8 + 5x^7 + 2x^6 - 5x^5 + 2x^4 + x^3 - x^2
s=s/p
s(x) = 3x^4 + x^3 + 2x^2 - 1
y=~s
y(x) = -3x^4 - x^3 - 2x^2 + 1
t=s-r
t(x) = -4x^5 + x^3 - x^2
p=p*p
p(x) = 16x^10 - 8x^8 + 8x^7 + x^6 - 2x^5 + x^4
p=p*p
p(x) = 256x^20 - 256x^18 + 256x^17 + 96x^16 - 192x^15 + 80x^14 + 48x^13 - 47x^12 + 12x^11 + 6x^10 - 4x^9 + x^8
a: 3 4 5 -1 3 1 2
a(x) = 4x^5 - x^3 + x^2
b: 2 1 1 1 0
b(x) = x + 1
u=(a+q)*b
u(x) = 4x^6 + 7x^5 + 3x^4 + 3x^3 + 3x^2 - x - 1
v=(a+q)/b
v(x) = 4x^4 - x^3 + x^2 + 2x - 2
w=(a+q)%b
w(x) = 1
b: 2 -1 2 9 0
b(x) = -x^2 + 9
w=(a+q)%b
w(x) = 324x + 269
u=u-(a+q)%b
u(x) = 4x^6 + 7x^5 + 3x^4 + 3x^3 + 3x^2 - 325x - 270

As linhas em negrito foram digitadas pelo usuário da calculadora. As demais linhas são geradas pela calculadora e formam a saída do programa.

Cada linha da entrada contém um comando para a calculadora. Todo comando começa com uma letra minúscula de 'a' a 'w'. Essa letra identifica uma variável da calculadora. O comando "v?" (uma variável da calculadora seguida do caractere "?") é um comando de consulta que imprime o polinômio associado à variável especificada. No início da sua execução, a calculadora inicializa com polinômios nulos todas as variáveis de 'a' a 'w'. (Seu programa deve fazer isso!) Por esse motivo, a consulta "a?" imprime a informação a(x) = 0" (a é um polinômio nulo). A primeira das consultas "p?" imprime informação análoga.

Um comando da forma "v: n <lista de n pares>" atribui à variável v o polinômio cujos termos não nulos são especificados por uma lista de n pares de números. Em cada um desses pares de números, o primeiro elemento é o coeficiente do termo (um número real) e o segundo elemento é o expoente do termo (um número inteiro não negativo). Assim, o comando "p: 3 1 2 -1 3 4 5" atribui à variável p um polinômio com três termos não nulos (o polinômio x² - x³ + 4x⁵). Em resposta a esse comando, a calculadora imprime o polinômio atribuído à variável p (a informação p(x) = 4x^5 - x^3 + x^2). Note que a lista de pares não precisa ser fornecida em ordem decrescente de expoente. No comando "q: 4 3 4 -1 0 1 3 2 2" os pares são fornecidos numa ordem arbitrária, mas os termos do polinômio atribuído à variável q aparecem em ordem decrescente de expoente (q(x) = 3x^4 + x^3+ 2x^2 - 1).

Um comando da forma "v=s+t", ou da forma "v=s-t", ou da forma "v=s*t", ou da forma "v=s/t", ou da forma "v=s%t" atribui à variável v o polinômio resultado de uma operação (soma, subtração, multiplicação, quociente ou resto) aplicada aos polinômios associados às variáveis s e t. Similarmente, um comando da forma "v=~s" atribui à variável v o polinômio resultado da negação do polinômio associado à variável s. Em resposta a comandos assim, a calculadora imprime o polinômio atribuído à variável v. O exemplo acima contém vários comandos desse tipo. Note que a mesma variável pode aparecer nos dois lados da atribuição ("p=p*p").

Na verdade, a nossa calculadora aceita expressões arbitrárias (válidas) com os operadores acima, conforme mostramos no exemplo.

Implementação do Programa Cliente

Note que o segundo caractere de cada comando ('?', ':', ou '=') define o tipo do comando. O primeiro caractere especifica a variável afetada pelo comando. Você pode usar esses fatos para simplificar a implementação do seu programa cliente.

Para implementar as variáveis da calculadora, utilize um vetor com 23 posições (uma para cada letra minúscula de 'a' a 'w'), que contenha em cada posição uma referência para um polinômio.

Mais especificamente, seu programa cliente deve manter um vetor

    polinomio var[23]; /* O tipo polinomio é o definido pela biblioteca. */

de modo que

var[0] seja o polinomio associado à variável cujo identificador é a,
var[1] seja o polinomio associado à variável cujo identificador é b,
var[2] seja o polinomio associado à variável cujo identificador é c, etc.

Em outras palavras, as 23 variáveis da calculadora (a, b, c, ..., w) são implementadas pelas 23 posições do vetor var (var[0], var[1], var[2],..., var[22]). Dessa forma pode-se ter acesso a um polinômio de modo bem eficiente, a partir da letra minúscula que identifica o polinômio.

No início da execução do programa, todas as posições do vetor var devem ser inicializadas com polinômios nulos. Para obter polinômios nulos, faça chamadas à função code>crie_monomio passando o valor zero no parâmetro coef.

Tome o seguinte cuidado com a leitura dos dados no seu programa cliente: leia cada linha da entrada até o último caractere da linha (o caractere '\n' que termina toda linha), incluindo esse caractere. Se você não fizer isso, quando você estiver querendo ler o primeiro caractere da próxima linha você acabará pegando o '\n' da linha anterior (ou até mesmo algum caractere que apareceu antes desse '\n', como por exemplo um espaço presente ao final da linha anterior). Para não ter esse tipo de problema, faça seu cliente ler toda linha até o fim, passando para a linha seguinte só depois de ler um '\n'! Para tanto, você pode usar a seguinte função:

void descarta_resto_da_linha() {
  char c;
  
  do {
    scanf("%c", &c); 
  } while (c != '\n' && c != EOF);
}

Faça o seu programa cliente chamar descarta_resto_da_linha no tratamento de todo comando da calculadora: depois de ler o último caractere útil de um comando, descarte o resto da linha da entrada.

Executável para você testar

Aqui você encontra, além do arquivo polinomio.h, os arquivos polinomio.o e calculadora.exe, um com a biblioteca pedida já compilada, e o outro com o executável do programa cliente. Encontra ainda uma versão para 64 bits do polinomio.o.

Recomendações

Utilize listas ligadas no seu programa para armazenar cada um dos polinômios. Se você não utilizar listas ligadas, o seu EP receberá nota zero.

Comece implementando o programa cliente utilizando a biblioteca disponível aqui. Para tanto, se o seu programa cliente está no arquivo ep2.c, então este seu arquivo deve começar com as seguintes linhas:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "polinomio.h"

e pode utilizar as funções da biblioteca polinomio.h. Para compilar o programa em ep2.c, escreva "gcc -Wall -ansi -pedantic polinomio.o ep2.c". Dessa maneira, a implementação será linkada com o seu programa cliente. (As opções "-Wall -ansi -pedantic" são as usuais que fazem o compilador dar mais avisos, ajudando você a debugar seu programa mais facilmente.)

Observe que sua calculadora terá que ser capaz de processar expressões infixas. Para tanto, ter´ que montar a posfixa correspondente a cada expressão infixa e usar a posfixa para fazer o cálculo da expressão.

A vantagem de implementar primeiramente o programa cliente é que este não usa listas ligadas! Tente ter uma versão funcionando do programa cliente por volta do dia 15 de setembro.

Uma vez implementado o programa cliente, passe à implementação da biblioteca. Esta sim vai utilizar listas ligadas! Escreva uma a uma as funções da biblioteca polinomio.h, e as teste uma a uma com o seu programa cliente.

Se a sua implementação da biblioteca está no arquivo polinomio.c, então, para obter um arquivo polinomio.o, basta você executar gcc -Wall -ansi -pedantic -c polinomio.c -o polinomio.o.

Divirta-se com o EP!

Entrega, prazos e observações

O EP é estritamente individual.
O EP é estritamente individual. Usaremos um sistema para detecão de EPs copiados.
O EP é estritamente individual. Alunos envolvidos em cola serão reprovados na disciplina sem mais, e seus nomes serão encaminhados para a Comissão de Graduação para demais providências.
Exercícios atrasados não serão aceitos.
Capriche na documentação do seu programa.
Coloque o cabeçalho usual em seu programa (como em MAC110), com nome, número USP, curso, data, nome do professor e identificação do EP (EP2)...
A entrega do programa consiste da entrega eletrônica de um arquivo compactado (com o programa tar, por exemplo) contendo os três arquivos do seu programa: polinomio.h (a interface da biblioteca), polinomio.c (a implementação da biblioteca) e calculadora.c (o programa cliente). Este arquivo deve ser entregue até dia 3 de outubro, inclusive.

Last modified: Thu Sep 23 11:29:43 BRT 2010