Este exercício-programa é uma continuação do exercício-programa anterior. Você escreverá um programa cujas entradas são uma seqüência de polinômios e uma sequência de expressões envolvendo esses polinômios. O programa deve calcular essas expressões e apresentar como saída os polinômios resultantes de cada uma das expressões. Será utilizada a biblioteca para manipulação de polinômios esparsos que você escreveu para o primeiro exercício-programa. Se você não fez o EP1 ou se o seu EP1 teve muitos problemas, você poderá usar esta solução do EP1 como base para o seu EP2.
O trabalho consistirá de três partes:
O programa que você escreverá na terceira parte será um cliente da biblioteca manipuladora de polinômios e do tipo de dados abstrato pilha, no sentido de que ele usará a biblioteca e o tipo pilha.
Esta parte é realmente simples. (Eu já devia ter pedido isto no EP1!) Adicione a seguinte função à interface da biblioteca:
Polinomio nega(Polinomio p); p e devolve como valor da função um
novo polinômio que é o produto de p por -1, ou seja
cada monômio do polinômio devolvido é igual a um monômio de
p com o coeficiente multiplicado por -1
Crie novas versões dos arquivos polinomio.h e
polinomio.c com essa função.
O método mais conhecido e eficiente para cálculo de expressões utiliza
pilhas. A terceira parte deste EP (o programa que calcula expressões com
polinômios) usará um tipo de dados abstrato pilha, que você deverá criar.
Nesta parte do EP você escreverá os arquivos pilha.h (a interface do
tipo de dados abstrato pilha) e pilha.c (a implementação desse tipo
de dados abstrato). Para que sua pilha seja genérica, considere que os
elementos empilhados e desempilhados são do tipo Item, cuja definição
(um typedef) está no arquivo item.h, e faça a interface e a
implementação da pilha incluirem o arquivo item.h.
Fica a seu critério decidir se o seu tipo de dados abstrato pilha será de
primeira classe ou não. De qualquer modo, a interface desse tipo de dados
abstrato deve conter as funções usuais de pilha. Caso você opte por um tipo
de dados que não seja de primeira classe, o seu arquivo pilha.h
deve ser assim:
#include "item.h" void inicializa(int n); /* Inicializa a pilha considerando que ela comportará no máximo n Itens. */ int vazia(); /* Devolve 1 se a pilha está vazia, 0 em caso contrário. */ void empilha(Item item); /* Empilha o item passado como parâmtro. */ Item espia_topo(); /* Devolve o Item que estiver no topo da pilha, sem desempilhá-lo. */ Item desempilha(); /* Desempilha um Item e o devolve como valor da função. */
Se você optar por um tipo de dados abstrato de primeira classe, a primeira
função deixará de ser inicializa e passará a ser
cria:
Pilha cria(int n); /* Devolve uma pilha recém-criada, com capacidade para no máximo n Itens. */
No caso do tipo de primeira classe, todas as demais funções receberão um
parâmetro adicional que especifica a Pilha sobre a qual se deseja
operar. Para que o tipo de dados seja abstrato, faça o parâmetro
Pilha ser opaco. Em outras palavras, não deixe informações sobre
a estrutura interna de uma Pilha vazarem para os clientes da
Pilha. Já no caso de um tipo pilha que não seja de primeira
classe, as variáveis usadas pela implementação da pilha não devem ser visíveis
fora do arquivo pilha.c.
Em qualquer caso (tipo de primeira classe ou não), a implementação do seu tipo de dados abstrato pilha deve ser vetorial.
Dica: Antes de usar o tipo pilha na próxima etapa, teste-o em um cenário bem simples. Escreva e rode um programa de testes que faz manipulações básicas sobre uma pilha de inteiros, de modo a verificar se as operações do tipo pilha funcionam corretamente.
A entrada para o programa cliente é um arquivo com duas partes. A primeira parte é uma seqüência de polinômios enquanto que a segunda parte é uma seqüência de expressões envolvendo esses polinômios. Para facilitar os testes, o programa cliente deve apresentar (imprimir) na saída não apenas o polinômio resultado de cada uma das expressões, mas também a versão posfixa de cada expressão. (Os resultados serão calculados a partir das versões posfixas das expressões.)
A primeira parte da entrada começa com uma linha contendo um número natural n. Este é o número de polinômios que aparecerão na seqüência. Cada uma das próximas n linhas especifica um polinômio no mesmo formato usado no EP1, com apenas uma diferença: a linha começa com uma letra minúscula, que é o identificador do polinômio. Por exemplo, um arquivo de entrada com esta primeira parte
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 4 polinômios:
p = x2-x3+4x5
q = -1+2x2+x3+3x4
t = x
z = x-x2
Após a leitura de cada polinômio do arquivo de entrada, imprima-o num formato
semelhante ao apresentado acima, mas com a exponenciação denotada por
"^" (x^2 em vez de x2, por
exemplo). Use a função imprime da biblioteca. Não se esqueça de
antes imprimir o identificador do polinômio!
A segunda parte da entrada consiste de uma seqüência de expressões envolvendo
os identificadores que apareceram na primeira parte e os operadores
"+", "-", "*", "'"
(linha), usado para a derivada, e "~", que denota o menos unário. (O uso de
símbolos diferentes para a subtração e para o menos unário simplifica as
coisas.) As expressões podem ter parênteses. Cada expressão aparece em uma
linha separada. Mais adiante falaremos sobre as questões da precedência e da
associatividade dos operadores. Considere agora o seguinte exemplo de
segunda parte (a primeira parte da entrada é a que foi vista 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. Para
lê-la, você pode usar o comando fscanf("%s", expr), onde
expr é um vetor de caracteres.
A precedência determina qual operador "precede" o outro, ou seja, qual deve ser efetuado primeiro. Esta é ordem de precedência dos operadores usados neste EP:
'"~"*"+" e "-"
(empatados, ou seja, com a mesma precedência)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 "-".
A associatividade dos operadores binários é sempre da esquerda para a direita. Ou seja, na expressão
a+b-c+d
o primeiro "+" é efetuado, depois o "-" e finalmente
o segundo "+ ".
Você precisará associar os polinômios montados na primeira parte aos seus
identificadores. (As expressões são dadas em termos dos identificadores!)
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 uma referência para o polinômio.
Mais especificamente, seu programa deve manter um vetor
Polinomio polinomio[26]; /* O tipo Polinomio é o definido pela biblioteca. */
polinomio[2] é o Polinomio
cujo identificador é c, ou é NULL, caso não exista
polinômio com o identificador c. Pode-se assim ter acesso a um
polinômio de forma bem eficiente a partir do identificador do polinômio.
O programa cliente usará uma pilha em duas ocasiões: durante a conversão de
cada expressão da notação infixa para a posfixa (a pilha dos operadores) e
durante o cálculo da expressão (a pilha de valores). Na pilha de operadores,
os itens empilhados e desempilhados são chars. Na de valores, os
itens empilhados e desempilhados são Polinomios.
A seguinte definição permite que se use uma mesma pilha ora com caracteres,
ora com Polinomios:
typedef union {
char ch;
Polinomio pol;
} Item;
Uma union é como uma struct, com a diferença que os
diversos campos têm o mesmo endereço de memória, ou seja, eles ocupam o mesmo
espaço e portanto não podem ser usados simultaneamente. Especificamente, a
union acima ocupa o espaço de um Polinomio, que é o
mais "espaçoso" de seus campos. Os campos de uma union podem ser
acessados da mesma forma que os campos de uma struct.
Para utilizar a pilha com essa definição de Item, antes de
empilhar um caracter ou Polinomio você precisará copiá-lo
para o campo adequado de um Item. Para empilhar um caracter
c, faça algo assim:
Item item; /* uma variável auxiliar do tipo Item */
...
item.ch = c;
empilha(item); /* este exemplo supõe que o tipo de dados pilha não é de primeira classe */
Analogamente, quando empilhar um Polinomio p, faça:
item.pol = p;
empilha(item);
Inversamente, lembre-se que cada Item devolvido pelas funções
espia_topo e desempilha é neste caso uma
union. Se você quiser olhar para o valor guardado nesse
Item como um caracter, pegue o campo ch do
Item. Se você quiser olhar o valor guardado nesse
Item como um Polinomio, pegue o campo
pol do Item.
Exemplos:
while (desempilha().ch != '(') {
...
}
ou
Polinomio p, q;
q = desempilha().pol;
p = desempilha().pol;
soma(p,q);
Se você tiver dúvidas sobre o uso de unions, mande suas dúvidas
para o fórum de
discussão da disciplina ou pergunte na sala de aula.
O programa cliente deve ler a entrada padrão, caso ele tenha sido ativado sem nenhum argumento na linha comando, ou o arquivo cujo nome foi passado como argumento na linha de comando. Assim, no Linux, a linha de comando
./cliente
faz o programa cliente usar como arquivo de entrada a entrada padrão, que neste caso é o teclado. Já a linha de comando
./cliente arq_entrada
faz o programa cliente usar como arquivo de entrada o arquivo
arq_entrada. Finalmente, a linha de comando
./cliente < arq_entrada
faz o programa cliente usar como arquivo de entrada a entrada padrão
redirecionada, que neste caso é o arq_entrada.
Além de usar a biblioteca de manipulação de polinômios e o tipo de dados
abstrato pilha, o programa cliente (arquivo cliente.c) deve
conter as seguintes funções:
void converte(char original[], char posfixa[]);original, contendo uma expressão como as
dadas no arquivo de entrada, e devolve na string posfixa a
expressão posfixa correspondente.Polinomio avalia(char posfixa[], Polinomio polinomio[]);posfixa e o vetor polinomio
definido acima, e devolve um novo
Polinomio, recém-criado, que é o resultado da expressão em
posfixa.Este trabalho deve ser entregue até 28/10, através do sistema Paca/Moodle.
ep2-<seu-número-USP.tar.gz> ou
ep2-<seu-número-USP.zip>.
Por exemplo: ep1-12345678.zip..tar.gz ou .zip. (Exemplo:
ep2-12345678.) Todos os arquivos desempacotados devem
estar dentro desse diretório..h ou .c necessários para gerar o programa
cliente a partir do zero. Pelo menos os seguintes arquivos deverão
estar presentes: polinomio.h, polinomio.c,
pilha.h, pilha.c, item.h e
cliente.c. Inclua também quaisquer outros arquivos
.h ou .c que você utilizar para funções
auxiliares compiladas separadamente. Por exemplo, se você tiver um
módulo compilado separadamente contendo apenas a função
mallocX, então você deverá entregar os arquivos
mallocx.h e mallocx.c.
.h ou .c devem ter
um cabeçalho como o seguinte:
/**********************************************************/
/* Aluno: Fulano de Tal */
/* Número USP: 12345678 */
/* Exercício-Programa 2 -- Expressões com Polinômios */
/* MAC122 -- BMAC -- 2008 -- Professor: Reverbel */
/* Compilador: ... (DevC++ ou gcc) versão ... */
/**********************************************************/
gcc,
com as opções "-Wall -ansi -pedantic -O2".gcc,
passe ao compilador (na linha de comando) as opções
"-Wall -ansi -pedantic -O2".
Caso você use o DevC++, clique em "Ferramentas" (ou
"Tools") e "Opções do Compilador" (ou "Compiler
Options") e, na tela de opções do compilador, marque como
selecionada a opção "Adicione os seguintes comandos quando chamar o
compilador" (ou "Add the following commands when calling
compiler"). Na caixa de texto que aparece logo depois dessa opção,
digite "-Wall -ansi -O2". (Não use "-pedantic"
com o DevC++.)
Last modified: Wed Oct 29 20:22:17 BRST 2008