多项式乘法
Time Limit:1s Memory Limit:500k
Total Submit:215 Accepted:94


--------------------------------------------------------------------------------

Problem
请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定： (1) 代数多项式表达式中只涉及一个代数符号a； (2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。 (3) 常数项以外的各项都是ya^x的形式，其中x为该项的系数，而y是该项的指数。1=x 时，不得简写成ya^，应写成ya^1。而1=y时，不得简写成a^x，应写成1a^x。

Input
输入：每行一个含有乘法的代数多项式表达式。本题有多组数据。

Output
输出：每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。不允许出现不必要的空白字符。

Sample Input
(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)* (5a^1+1)

Sample Output
20a^3+17a^2+11a^1+2
25a^2+10a^1+1


#include<iostream.h>
struct polynode
{
    polynode *next;
    int a,e;//ax^e
};
class poly
{
protected:
    polynode *head,*tail;
    void additem(char*);
    void add(int,int);
public:
    poly(){head=tail=NULL;};
    poly(char*);
    poly(poly&);
    ~poly();
    void display();
    friend poly operator*(poly&,poly&);
};
void poly::additem(char *str)
{
    int a=0,e=0;
    while(*str!='a'&&*str!='\0')
    {a=a*10+*str-'0';++str;}
    if(*str=='a')
    {
        str+=2;
        while(*str!='\0')
        {e=e*10+*str-'0';++str;}
    }
    polynode *p=new polynode;
    p->a=a;
    p->e=e;
    p->next=NULL;
    if(tail==NULL)
    {
        head=p;
    }
    else
    {
        tail->next=p;
    }
    tail=p;
}
poly::poly(char *str)
{
    char *prestr;
    head=tail=NULL;
    while(1)
    {
        prestr=str;
        while(*str!='+'&&*str!='\0')++str;
        if(*str=='\0')
        {
            additem(prestr);
            return;
        }
        *str='\0';
        additem(prestr);
        ++str;
    }
}
poly::poly(poly& t)
{
    polynode *p;
    if((p=t.head)==NULL)
    {
        head=tail=NULL;
        return;
    }
    head=tail=new polynode;
    head->a=p->a;
    head->e=p->e;
    head->next=NULL;
    p=p->next;
    while(p)
    {
        add(p->a,p->e);
        p=p->next;
    }
}
poly::~poly()
{
    polynode *p=head,*prep;
    while(p)
    {
        prep=p;
        p=p->next;
        delete prep;
    }
}
void poly::display()
{
    polynode *p=head;
    while(1)
    {
        cout<<p->a;
        if(p->e!=0)
            cout<<"a^"<<p->e;
        p=p->next;
        if(p)cout<<"+";
        else break;
    }
    cout<<endl;
}
void poly::add(int a,int e)
{
    polynode *p=head;
    if(p==NULL)
    {
        head=tail=new polynode;
        tail->a=a;
        tail->e=e;
        tail->next=NULL;
    }
    else
    {
        while(p&&p->e!=e)p=p->next;
        if(p==NULL)
        {
            p=new polynode;
            p->a=a;
            p->e=e;
            p->next=NULL;
            tail->next=p;
            tail=p;
        }
        else
        {
            p->a+=a;
        }
    }
}
poly operator*(poly& f1,poly& f2)
{
    int a,e;
    poly rst;
    polynode *p,*q;
    if(f1.head==NULL||f2.head==NULL)return poly("0");
    for(p=f1.head;p!=NULL;p=p->next)
        for(q=f2.head;q!=NULL;q=q->next)
        {
            a=p->a*q->a;
            e=p->e+q->e;
            if(a==0)continue;
            rst.add(a,e);
        }
    return rst;
}
void main()
{
    char str1[256]="5a^1+1";
    char str2[256]="5a^1+1";
    poly a(str1),b(str2);
    poly c=a*b;
    c.display();
}

评论