這個是我們的計算機程式設計的作業, 應版主老大要求就 post 過來啦. :)
作業的題目在 http://www.csie.ntu.edu.tw/~cprog/ 可以看得到.
/* Copyright (C) 1998 Chia-liang Kao
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
*/
include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ABS(a) ((a)>0)?(a):(-(a))
struct frac {
int num, den;
};
struct poly {
struct poly *next;
struct frac coef;
int exp;
};
int
gcd(a, b)
{
int r;
while(b) {
r = a % b;
a = b, b =r;
}
return a;
}
void
abbr(struct frac *x)
{
int d = gcd(x->num, x->den);
x->num /= d, x->den /= d;
if(x->den < 0)
x->den = -x->den, x->num = -x->num;
}
void
prepare_parse(char *p)
{
char bbuf[512], *cp = bbuf, *orig = p;
if(*p == 'X')
*(cp++) = '1';
do {
*cp = *p;
if((*p == '-' || *p == '+') && *(p+1) == 'X')
*(++cp) = '1';
++cp, ++p;
}
while(*p);
*cp = 0;
strcpy(orig, bbuf);
}
int
dcmp(struct poly *a, struct poly *b)
{
return b->exp - a->exp;
}
void fplus(struct frac *a, struct frac *b);
void
add_poly(struct poly **head, struct poly *ptr, int (*cmp) (struct poly *, struct
poly *))
{
ptr->next = 0;
if(!*head)
*head = ptr;
else if(cmp(*head, ptr) >= 0)
ptr->next = *head, *head = ptr;
else {
struct poly *p;
for(p = *head; p->next&&cmp(p->next, ptr) < 0; p=p->next);
if(p->next && !cmp(p->next, ptr)) {
fplus(&p->next->coef, &ptr->coef);
}
else {
ptr->next = p->next;
p->next = ptr;
}
}
}
struct poly *
parse_poly(char *p)
{
int c;
struct poly *head = 0;
while(*p && (c = strtol(p, &p, 10))) {
int e = 1;
struct poly *ptr = (struct poly *)malloc(sizeof(struct poly));
if(*p != 'X')
e = 0;
else
++p;
if(*p == '^') {
if(!(e = strtol(p+1, &p, 10))) {
fputs("parse error\n", stderr);
return 0;
}
}
ptr->coef.num = c, ptr->coef.den = 1;
ptr->exp = e;
add_poly(&head, ptr, dcmp);
}
return head;
}
void
display_coef(struct frac *f, char sign, int con)
{
char positive = (f->num >= 0)? 1 : 0;
char single = (f->den == 1)? 1 : 0;
if(!con && single && (f->num == 1 || f->num == -1)) {
if(sign)
fputc(positive?'+':'-', stdout);
return;
}
if(!positive || sign)
printf("%c", (f->num >= 0)? '+' : '-');
if(single)
printf("%d", ABS(f->num));
else
printf("(%d/%d)", ABS(f->num), f->den);
}
int
display_term(struct poly *pterm, char sign)
{
if(!pterm->coef.num) {
return 0;
}
display_coef(&pterm->coef, sign, (pterm->exp == 0));
if(pterm->exp >= 1)
fputc('X', stdout);
if(pterm->exp > 1)
printf("^%d", pterm->exp);
return 1;
}
void
print_poly(struct poly *phead)
{
struct poly *p;
int something = 0;
for(p = phead; p; p=p->next)
if(display_term(p,(p==phead)?0:1) && !something)
something = 1;
if(!something)
fputc('0', stdout);
}
void
do_diff(struct poly *phead)
{
struct poly *p;
for(p = phead; p; p=p->next)
p->coef.num*=p->exp, --p->exp;
}
void
do_int(struct poly *phead)
{
struct poly *p;
for(p = phead; p; p=p->next) {
++p->exp, p->coef.den *= p->exp;
abbr(&p->coef);
}
}
void
fplus(struct frac *a, struct frac *b)
{
int g = gcd(a->den, b->den), af = b->den / g, bf = a->den / g;
a->den *= af, a->num *=af;
b->den *= bf, b->num *=bf;
a->num += b->num;
abbr(a);
}
void
eval(struct poly *p, struct frac *f)
{
struct frac cf, tf = {1,1};
int i;
for(;p;p=p->next) {
cf = p->coef;
for(i=0;i<p->exp;++i)
cf.num *= f->num, cf.den *= f->den;
fplus(&tf, &cf);
}
*f = tf;
}
int
main()
{
struct poly *poly;
char buf[256], *cp;
int from, end;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
while(fgets(buf, 256, stdin)) {
char sint = 0;
(void)strtok(buf, "\n");
if(*buf != 'I' && *buf != 'D') {
fputs("cmd must be `I' or `D'\n", stderr);
continue;
}
if(*buf == 'I' && buf[1] == '[') {
sint = 1;
if(!(cp = strchr(buf+2, ']'))) {
fputs("] not present\n", stderr);
continue;
}
sscanf(buf + 1, "[%d,%d]", &from, &end);
cp = strtok(cp + 1, " \t");
}
else
cp = strtok(buf+1, " \t");
prepare_parse(cp);
if(!strcmp(cp, "0")) {
fputs((*buf == 'D' || sint)?"0\n":"C\n", stdout);
continue;
}
if(!(poly = parse_poly(cp)))
continue;
if(*buf == 'D') {
do_diff(poly);
print_poly(poly);
fputc('\n', stdout);
}
if(*buf == 'I') {
do_int(poly);
if(sint) {
struct frac b,e;
e.num = end, e.den = 1;
b.num = from, b.den = 1;
eval(poly, &e);
eval(poly, &b);
b.num = -b.num;
fplus(&e, &b);
display_coef(&e, 0, 1);
fputc('\n', stdout);
}
else {
print_poly(poly);
fputs("+C\n", stdout);
}
}
}
return 0;
}
--
`開學了, 我又要開始認真了' -- L. C. Kung, 1997
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: snoopy.csie.ntu