/////////////////////////////////////////////////    
//   程序功能： 實現一元多項式的四則運算        //    
/////////////////////////////////////////////////    
   
   
#include <STDIO.H>    
#include <STDLIB.H>    
//定義結構體 ；    
struct polynode                                          
{   
    float coef ;   
    int exp  ;   
    struct polynode *next ;   
};   
typedef struct polynode pointer ;   
   
void Output(pointer *a) ;   
   
//指數比較函數 ；    
char Compare(int x, int y)                               
{   
     if(x > y)   
        return ('>');   
     if(x < y)   
        return ('<');   
     else   
        return ('=');   
}   
   
pointer * Attch(float c, int e, pointer *d)   
{   
    pointer *x ;   
    x = (pointer *)malloc( sizeof(pointer) ) ;   
    x->next = NULL ;    
    x->coef = c ; x->exp = e ; d->next = x ;   
    return x ;   
}   
   
//一元多項式的加法運算 ；    
pointer * Poly_ADD(pointer *a, pointer *b)                
{   
    pointer *p , *q , *d , *c ;   
    float x=0 ;   
    p = a ; q = b ;   
    c = (pointer *)malloc( sizeof(pointer) ) ;   
    c->next = NULL ;   
    d = c ;   
    while((p!=NULL)&&(q!=NULL))   
        switch(Compare(p->exp, q->exp))   
        {   
            case '=' : x = p->coef + q->coef ;   
                       if(x)  d = Attch(x, p->exp, d) ;   
                       p = p->next ; q = q->next ;   
                       break ;   
            case '>' : d = Attch(p->coef, p->exp, d) ;   
                       p = p->next ;   
                       break ;   
            case '<' : d = Attch(q->coef, q->exp, d) ;   
                       q = q->next ;   
                       break ;   
            default  : break ;   
        }   
    while(p != NULL)   
    {   
        d = Attch(p->coef, p->exp, d) ;   
        p = p->next ;   
    }   
    while(q != NULL)   
    {   
        d = Attch(q->coef, q->exp, d) ;   
        q = q->next ;   
    }   
    d->next = NULL ; p = c ; c = c->next ;   
    printf("運算結果是：");   
       
    free(p) ;     
    return c ;   
}   
   
//一元多項式的減法運算 ；    
pointer * Poly_SUB(pointer *a, pointer *b)                  
{   
    pointer *p , *q , *d , *c ;   
    float x=0 ;   
    p = a ; q = b ;   
    c = (pointer *)malloc( sizeof(pointer) ) ;   
    c->next = NULL ;   
    d = c ;   
    while((p!=NULL)&&(q!=NULL))   
        switch(Compare(p->exp, q->exp))   
        {   
            case '=' : x = p->coef - q->coef ;   
                       if(x)  d = Attch(x, p->exp, d) ;   
                       p = p->next ; q = q->next ;   
                       break ;   
            case '>' : d = Attch(p->coef, p->exp, d) ;   
                       p = p->next ;   
                       break ;   
            case '<' : d = Attch(-q->coef, q->exp, d) ;   
                       q = q->next ;   
                       break ;   
            default  : break ;   
        }   
    while(p != NULL)   
    {   
        d = Attch(p->coef, p->exp, d) ;   
        p = p->next ;   
    }   
    while(q != NULL)   
    {   
        d = Attch(-q->coef, q->exp, d) ;   
        q = q->next ;   
    }   
    d->next = NULL ; p = c ; c = c->next ;   
    printf("運算結果是：");   
       
    free(p) ;     
    return c ;   
}   
   
//一元多項式的乘法運算 ；    
pointer * Poly_MUL(pointer *a, pointer *b)                        
{   
    pointer *p , *q , *c , *d , *e , *g ;   
    float coef=0 ;   
    int exp=0 ;   
    p = a ; q = b ;   
    c = NULL ;   
       
    while(p!=NULL)   
    {   
        q = b ;   
        e = (pointer *)malloc( sizeof(pointer) ) ;   
        e->next = NULL ; d = e ;   
        while(q!=NULL)   
        {   
            coef = p->coef * q->coef ;   
            exp = p->exp + q->exp ;   
            d = Attch(coef, exp, d) ;   
            q = q->next ;   
        }    
        d->next = NULL ;   
        e = e->next ;       
        c = Poly_ADD(c, e) ;   
        g = e ;   
        free( e );     
        p = p->next ;   
    }   
    printf("運算結果是：");   
    return c ;   
}   
       
//一元多項式的除法運算 ；    
pointer *Poly_DIV(pointer *p, pointer *q)                       
{   
     pointer *a , *b , *d , *f ;   
     float m ;   
     int   n ;   
     a =  (pointer *)malloc( sizeof(pointer) ) ;   
     a->next = NULL ; b = a ;   
     f = p ;   
     if(q->coef == 0)   
     {   
         printf("\a您輸入的多項式B為0，無法進行除法運算。\n");   
         return NULL ;   
     }   
     else   
     {   
         do   
         {   
            d = (pointer *)malloc( sizeof(pointer) ) ;   
            d->next = NULL ;   
            m = (float)(f->coef) / (q->coef) ;   
            n = (f->exp) - (q->exp) ;   
            b = Attch(m, n, b) ;   
            b->next = NULL ;   
            d = Poly_MUL(q, b) ;   
            f = Poly_SUB(f, d) ;   
            free(d) ;   
         }while((f->exp) >= (q->exp)) ;   
         printf("余式是：") ;   
         Output(f) ;   
         printf("商式是：") ;   
         a = a->next ;      
         return a ;   
     }   
}       
            
//一元多項式的輸出 ；    
void Output(pointer *a)                                    
{   
    while(a != NULL)   
    {   
        printf("(%.1f,%d) ", a->coef, a->exp);   
        a = a->next ;   
    }   
    printf("\n\n");   
}   
   
   
int main()   
{   
    float coef=0 ;    
    int exp=0 ;   
    int choice=0 ;   
    pointer *poly_A , *poly_B , *oper_A , *oper_B , *link_A , *link_B , *rezult ;   
       
    do{   
        poly_A = (pointer *)malloc( sizeof(pointer) ) ;   
        poly_A->next = NULL ;   
        oper_A = link_A = poly_A ;   
        poly_B = (pointer *)malloc( sizeof(pointer) ) ;   
        poly_B->next = NULL ;   
        oper_B = link_B = poly_B ;   
   
 
        printf("加法請按 1\n");   
        printf("減法請按 2\n");   
        printf("乘法請按 3\n");   
        printf("除法請按 4 \n");   


        scanf("%d", &choice);   
        if(choice==0)   
            return 0 ;   
        else if(choice<=4 && choice>=0)   
        {      
            printf("請輸入多項式 A <以 0 0 結尾> ：\n");   
            while( scanf("%f%d", &coef, &exp) != EOF )   
            {    
                if( coef==0 && exp==0 )   
                {   
                    link_A->next = NULL ;   
                    break ;   
                }   
                else   
                {   
                    oper_A->coef = coef ;   
                    oper_A->exp = exp ;   
                    link_A->next = oper_A ;   
                    link_A = link_A->next ;   
                    oper_A = (pointer *)malloc(sizeof(pointer)) ;   
                }   
            }   
       
            printf("請輸入多項式 B <以 0 0 結尾> ：\n");   
            while( scanf("%f%d", &coef, &exp) != EOF )   
            {   
                if( coef==0 && exp==0 )   
                {   
                    link_B->next = NULL ;   
                    break ;   
                }   
                else   
                {   
                    oper_B->coef = coef ;   
                    oper_B->exp = exp ;   
                    link_B->next = oper_B ;   
                    link_B = link_B->next ;   
                    oper_B = (pointer *)malloc(sizeof(pointer)) ;   
                }   
            }   
   
            switch(choice)   
            {   
                case 1 : rezult = Poly_ADD( poly_A, poly_B );   
                         break ;   
                case 2 : rezult = Poly_SUB( poly_A, poly_B );   
                         break ;   
                case 3 : rezult = Poly_MUL( poly_A, poly_B );   
                         break ;   
                case 4 : rezult = Poly_DIV( poly_A, poly_B );   
                         break ;   
                default : break ;   
            }   
            Output( rezult );   
            free( poly_A );   
            free( poly_B );   
            }   
        else   
            printf("對不起，您的選擇超出范圍。\n");   
    }while(choice != 0) ;   
   
    return 0 ;   
}