1482 —— 二元多项式

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

26

二元多项式

Problem Description给你多个二元多项式和一个操作符,让你输出操作符操作这些二元多项式之后的结果。Input首先输入二元多项式的个数n和操作符号(‘+’,‘*’);后面n行输入每一个多项式。多组输入,当n=0的时候结束输入。(n<5,二元多项式的长度小于1000,二元多项式都是由x,y,^,数字,’+’组成的)Output输出操作之后的结果。(输出的顺序按照:x^2>x>xy^2>xy>y^2>y>常数)Sample Input
2 +
3x+4y^2+3xy+6x^10y^2+1
2x+6y
0
Sample Output
6x^10y^2+5x+3xy+4y^2+6y+1
Hint

对于排序的要求:
1、x的指数大的在前面
2、x的指数相同的时候,分两种情况:
一种是x的指数不为零,此时y指数为零的在前面,否则,y指数大的在前面
一种是x的指数为零,此时y指数大的在前面(此时y指数为0,代表常数,在最后)

#include 
using namespace std;
struct Node
{int x;//x的指数int y;//y的指数int coef;//系数Node* next;//指向下一个单项式Node();//构造方法
};
Node::Node()
{x = 0;y = 0;coef = 0;next = NULL;
}
//生成结点
Node* Create_Node(int x, int y, int coef)
{Node* p = new Node();p->x = x;p->y = y;p->coef = coef;p->next = NULL;return p;
}
//比较相对位置的前后,p在q前面,返回1;在q后面返回-1;是同类项返回0
int Equal(Node* p, Node* q)//p、q都非空
{if (p->x == q->x){if (p->y == q->y)return 0;if (p->x){if (p->y == 0 || (q->y && p->y > q->y))return 1;elsereturn -1;}else//x指数是0{if (p->y > q->y)return 1;elsereturn -1;}}else if (p->x > q->x)return 1;elsereturn -1;
}
//生成二元多项式
Node* Create_Link (string s)
{Node* head = new Node();Node* myback = head;int len = s.length();int x = 0;int y = 0;int coef = 0;int base = 1;int data = 0;//临时存储数字for (int i = len - 1; i >= 0; i--)//从后面向前扫描是为了方便计算系数和指数{switch (s[i]){//遇到+的时候,将单项式生成结点,并插入多项式的链表中。case '+':{//生成结点存储数据,除了第一个单项式之外的式子if (data == 0){if (x || y)coef = 1;elsecoef = 0;}else{coef = data;}if (coef != 0){Node* p = Create_Node(x, y, coef);while (myback->next && (Equal(myback->next, p) > 0)){myback = myback->next;}p->next = myback->next;myback->next = p;myback = head;}x = 0;y = 0;coef = 0;data = 0;base = 1;break;}//遇到^的时候,存储x,y的指数case '^':{//遇到^,data肯定不是0 or 1if (s[i - 1] == 'x'){x = data;data = 0;base = 1;i = i - 1;}else if (s[i - 1] == 'y'){y = data;data = 0;base = 1;i = i - 1;}break;}//因为遇到^的时候,跳过了前面的x or y,所以遇到x or y的时候表明后面没有^,即x,y的指数是1case 'x':{x = 1;break;}case 'y'://存储y的指数{y = 1;break;}default://数字的情况{data += (s[i] - '0') * base;base = 10 * base;break;}}}//生成第一个单项式的结点if (data == 0 && (x != 0 || y != 0)){Node* p = Create_Node(x, y, 1);while (myback->next && (Equal(myback->next, p) > 0)){myback = myback->next;}p->next = myback->next;myback->next = p;myback = head;x = 0;y = 0;coef = 0;data = 0;base = 1;}else{if (data != 0){Node* p = Create_Node(x, y, data);while (myback->next && (Equal(myback->next, p) > 0)){myback = myback->next;}p->next = myback->next;myback->next = p;myback = head;}x = 0;y = 0;coef = 0;data = 0;base = 1;}return head;
}
Node* Add (Node* head1, Node* head2)
{Node* p1 = head1->next;Node* p2 = head2->next;Node* temp;Node* head = new Node ();Node* tail = head;while (p1 && p2){if (Equal(p1, p2) == 0){if (p1->coef + p2->coef == 0)//同类项相加系数为0{temp = p1;p1 = p1->next;head1->next = p1;delete temp;temp = p2;p2 = p2->next;head2->next = p2;delete temp;}else//相加系数非零{Node* p = Create_Node(p1->x, p1->y, p1->coef + p2->coef);tail->next = p;tail = p;temp = p1;p1 = p1->next;head1->next = p1;delete temp;temp = p2;p2 = p2->next;head2->next = p2;delete temp;}}else if (Equal(p1, p2) > 0){tail->next = p1;tail = p1;p1 = p1->next;head1->next = p1;}else{tail->next = p2;tail = p2;p2 = p2->next;head2->next = p2;}}if (p1){tail->next = p1;}if (p2){tail->next = p2;}delete head1;delete head2;return head;
}
Node* Multiply_Single (Node* p1, Node* p2)
{Node* head = new Node();Node* tail = head;//p1是单项式Node* q = p2->next;while (q){Node* p = Create_Node(p1->x + q->x, p1->y + q->y, p1->coef * q->coef);tail->next = p;tail = p;q = q->next;}return head;
}
Node* Multiply_Multiple (Node* p1, Node* p2)
{Node* head = new Node();Node *p = p1->next;while (p){head = Add(head, Multiply_Single (p, p2));p = p->next;}return head;
}
void Print(Node* head)
{Node* p = head->next;if (!p)cout << 0 << endl;else{while (p){//输出多项式,考虑的情况比较多//首先如果不是常数,系数1不显示if (p->coef != 1){cout << p->coef;}else if (p->x == 0 && p->y == 0)cout << p->coef;//如果指数是1,不显示指数,如果指数是0,连未知量也不显示if (p->x != 1 && p->x != 0){cout << "x^" << p->x;}else if (p->x == 1)cout << "x";if (p->y != 1 && p->y != 0){cout << "y^" << p->y;}else if (p->y == 1)cout << "y";p = p->next;if (p)cout << "+";elsecout << endl;}}
}
int main()
{int n;for (; cin >> n && n != 0;){char operation;cin >> operation;Node* head;if (operation == '+'){string s;cin >> s;head = Create_Link(s);for (int i = 0; i < n - 1; i++){cin >> s;Node *p = Create_Link(s);head = Add(head, p);}}else{string s;cin >> s;head = Create_Link(s);for (int i = 0; i < n - 1; i++){cin >> s;Node *p = Create_Link(s);head = Multiply_Multiple(head, p);}}Print(head);}
}