二元多项式

亦凉 2022-08-18 02:24 88阅读 0赞

## 二元多项式 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

给你多个二元多项式和一个操作符，让你输出操作符操作这些二元多项式之后的结果。

## 输入 ##

首先输入二元多项式的个数n和操作符号（‘+’，‘\*’）；

后面n行输入每一个多项式。

多组输入，当n=0的时候结束输入。

（n<5,二元多项式的长度小于1000，二元多项式都是由x，y，^,数字，’+’组成的）

## 输出 ##

输出操作之后的结果。

（输出的顺序按照：x^2>x>xy^2>xy>y^2>y>常数）

## 示例输入 ##

2 +
    3x+4y^2+3xy+6x^10y^2+1
    2x+6y
    0

## 示例输出 ##

6x^10y^2+5x+3xy+4y^2+6y+1

## 提示 ##

## 来源 ##

## 示例程序 ##

#include <cstdio>  
    #include <cstring>  
    #include <cstdlib>  
    #include <iostream>  
    #include <algorithm>  
    using namespace std;  
    char sen[1010];  
    struct N  
    {  
        int x1,x2,y1,y2;  
        struct N *next;  
    } mark[1010];  
      
    N *creat()  
    {  
        N *p = (struct N *)malloc(sizeof(struct N));  
        p->next = NULL;  
        return p;  
    }  
      
    void insert_mul(N *head,N *p)  
    {  
        p->next = head->next;  
        head->next = p;  
    }  
      
    void insert_add(N *head,N *p)  
    {  
        N *q1 = head;  
        N *q2 = head->next;  
        while(q2 != NULL)  
        {  
            if(q2->x2 == p->x2 && q2->y2 == p->y2)  
            {  
                q2->x1 += p->x1;  
                return ;  
            }  
            if(p->x2 != 0 || p->y2 != 0)  
            {  
      
                if(q2->x2 < p->x2)  
                {  
                    break;  
                }  
                else if(q2->x2 == p->x2)  
                {  
                    if(p->y2 == 0)  
                        break;  
                    else if(q2->y2 < p->y2 && ( q2->y2 != 0 || (q2->x2 == 0 && q2->y2 == 0) ) )  
                        break;  
                }  
            }  
            q1 = q1->next;  
            q2 = q2->next;  
        }  
        p->next = q1->next;  
        q1->next = p;  
    }  
      
    int cal(char *s)  
    {  
        int ans,sum,l;  
        for(ans = 1,sum = 0,l = strlen(s) - 1; l >= 0; l--)  
        {  
            sum += ans*(s[l]-'0');  
            ans *= 10;  
        }  
        return sum;  
    }  
      
    void check_number(char *s,char order,struct N *head)  
    {  
        char num[30];  
        int mark,top;  
        int ans;  
        int i,l;  
        N *p = creat();  
        p->x1 = 0;  
        p->x2 = 0;  
        p->y1 = 0;  
        p->y2 = 0;  
        for(mark = 1,ans = 1,i = 0,l = strlen(s),top = 0; i <= l; i++)  
        {  
            if(i != l && '0' <= s[i] && s[i] <= '9')  
            {  
                num[top++] = s[i];  
            }  
            else  
            {  
                num[top] = '\0';  
      
                if(top != 0)  
                {  
                    if(mark == 1)  
                    {  
                        p->x1 = cal(num);  
                    }  
                    else if(mark == 2)  
                    {  
                        p->x2 = cal(num);  
                    }  
                    else if(mark == 3)  
                    {  
                        p->y1 = cal(num);  
                    }  
                    else if(mark == 4)  
                    {  
                        p->y2 = cal(num);  
                    }  
                }  
                top = 0;  
                if(s[i] == 'y')  
                    mark = 3;  
                else if(s[i] == '^')  
                    mark++;  
            }  
        }  
        if(p->x2 == 0)  
        {  
            for(i = 0; i < l; i++)  
            {  
                if(s[i] == 'x')  
                {  
                    p->x2 = 1;  
                    break;  
                }  
            }  
        }  
        if(p->y2 == 0)  
        {  
            for(i = 0; i < l; i++)  
            {  
                if(s[i] == 'y')  
                {  
                    p->y2 = 1;  
                    break;  
                }  
            }  
        }  
        if(p->x1 == 0)  
        {  
            if(p->x2 != 0 || p->y2 != 0)  
                p->x1 = 1;  
        }  
        if(order == '+')  
        {  
            insert_add(head,p);  
        }  
        else insert_mul(head,p);  
    }  
      
    void analysis(char order,N *head)  
    {  
        int i,l,top;  
        char s[50];  
        for(top = 0,i = 0,l = strlen(sen); i < l; i++)  
        {  
            if(sen[i] == '+')  
            {  
                s[top] = '\0';  
                check_number(s,order,head);  
                top = 0;  
            }  
            else  
            {  
                s[top++] = sen[i];  
            }  
        }  
        s[top] = '\0';  
        check_number(s,order,head);  
    }  
      
    void output(N *head)  
    {  
        N *p = head->next;  
        bool mark = false;  
        if(p != NULL)  
        {  
            if(p->x2 == 0 && p->y2 == 0 && p->x1 != 0)  
            {  
                cout<<p->x1;  
                mark = true;  
            }  
            else if(p->x1 != 0)  
            {  
                mark = true;  
                if(p->x1 != 1)  
                {  
                    cout<<p->x1;  
                }  
                if(p->x2 != 0)  
                {  
                    cout<<'x';  
                }  
                if(p->x2 > 1)  
                {  
                    cout<<'^'<<p->x2;  
                }  
                if(p->y2 != 0)  
                {  
                    cout<<'y';  
                }  
                if(p->y2 > 1)  
                {  
                    cout<<'^'<<p->y2;  
                }  
            }  
        }  
        else return ;  
        for(p = p->next ; p != NULL; p = p->next)  
        {  
      
            if(p->x2 == 0 && p->y2 == 0 && p->x1 != 0)  
            {  
                mark = true;  
                cout<<'+';  
                cout<<p->x1;  
            }  
            else if(p->x1 != 0)  
            {  
                mark = true;  
                cout<<'+';  
                if(p->x1 != 1)  
                {  
                    cout<<p->x1;  
                }  
                if(p->x2 != 0)  
                {  
                    cout<<'x';  
                }  
                if(p->x2 > 1)  
                {  
                    cout<<'^'<<p->x2;  
                }  
                if(p->y2 != 0)  
                {  
                    cout<<'y';  
                }  
                if(p->y2 > 1)  
                {  
                    cout<<'^'<<p->y2;  
                }  
            }  
        }  
        if(mark == false)  
            cout<<0;  
        cout<<endl;  
    }  
      
    void multi(N *head[20],int n)  
    {  
        N *p,*q;  
        int i;  
      
        for(i = 1; i < n; i++)  
        {  
            head[n+i-1] = creat();  
      
            if(i == 1)  
            {  
                p = head[0]->next;  
            }  
            else p = head[n+i-2]->next;  
            for(; p != NULL; p = p->next)  
            {  
                for(q = head[i]->next; q != NULL; q = q->next)  
                {  
                    N *temp = creat();  
                    temp->x1 = q->x1 * p->x1;  
                    temp->x2 = q->x2 + p->x2;  
                    temp->y1 = 0;  
                    temp->y2 = q->y2 + p->y2;  
                    insert_add(head[n+i-1],temp);  
                }  
            }  
        }  
        output(head[n+i-2]);  
    }  
      
    int main()  
    {  
        int i,n;  
        char ch;  
        while(cin>>n && n)  
        {  
            N *head[20];  
            for(i = 0; i < n; i++)  
            {  
                head[i] = creat();  
            }  
            cin>>ch;  
      
            memset(mark,0,sizeof(mark));  
      
            for(i = 0; i <  n; i++)  
            {  
                cin>>sen;  
                if(ch == '*')  
                {  
                    analysis(ch,head[i]);  
                }  
                else analysis(ch,head[0]);  
            }  
      
            if(ch == '+')  
            {  
                output(head[0]);  
            }  
            else if(ch == '*')  
            {  
                multi(head,n);  
            }  
        }  
        return 0;  
    }