题解 P2379 【整式的计算】
star_magic_young · · 题解
WARNING
如果想好好练习字符串,请认真推敲,用代码去模拟,不要骗分
(好吧,数据有点小问题,要特判一下)
思路
和P1981有着异曲同工之妙,暂且把它看做一个运算式处理(具体见我的博客).
但是这里是多项式运算.所以我们用一个结构体来存储每一个单项式,用一个下标从1到26的数组表示a,b...z的指数(数组第0位存储单项式前面的系数)(字符串的作用后面讲).
递归字符串,以符号为界分成两半,处理出多项式后进行运算.若为加,则把两个式子(数组)合并在一起;若为减,则加上第一个式子,和系数相反的第二个式子;若为乘,则把每一项"乘"起来(具体看代码).输出的时候就排个序,去重输出(合并同类项)
code
//注:此代码在linux下的emacs写成,格式丑轻喷
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct nn
{
int a[27];char zz[30];int x;
nn(){memset(a,0,sizeof(a));x=0;}
}z[10000]; //解释一下:a存每个字母的指数和前面的系数,zz用来排序,把a转成字符串,x为字符串个数
char cc[300];
int l;
inline nn getss(int l,int r) //把单项式取出来
{
nn a;int i=l;int xx=0,yy=1,zz=1;
if(cc[i]=='-') zz=-1,i++; //zz判符号
while(i<=r&&(cc[i]>=48&&cc[i]<=57)) {xx*=10;xx+=cc[i]-48;i++;} //把系数处理出来(考虑负数)
xx=max(xx,1); //判前面没数字(系数为±1)
a.a[0]=zz*xx;xx=0;
while(i<=r)
{
if(cc[i]>=97) {xx=cc[i]-96;yy=1;} //把字母取出来
else
{
yy=0;i++;
while(l<=r&&(cc[i]>=48&&cc[i]<=57)) {yy*=10;yy+=cc[i]-48;i++;}
i--; //把字母指数取出来
}
a.a[xx]=yy; //存到数组里
i++;
}
return a;
}
inline int findd(int l,int r) //找符号(+ - ×) 返回下标
{
int xx=-1,zzz=0,yyy=0;
for(int i=r;i>=l;i--)
{
if(!zzz&&cc[i]=='+') return i; //找到加号直接退出去
else if(!zzz&&cc[i]=='-'&&cc[i-1]!='('&&cc[i-1]!='[') return i; //找到减号(不是负号)退出去
else if(!zzz&&!yyy&&cc[i]=='*') {xx=i;yyy=999;} //找到乘号先记录
else if(cc[i]=='('||cc[i]=='[') zzz--;
else if(cc[i]==')'||cc[i]==']') zzz++; //是否在括号内(zzz==0在括号外)
}
return xx;
}
inline int ys(int l,int r,nn a[]) //处理函数返回多项式的项数
{
int jj=0;
int mid=findd(l,r); //取符号
if(mid==-1) //没符号
{
if((cc[l]=='('&&cc[r]==')')||(cc[l]=='['&&cc[r]==']')) return ys(l+1,r-1,a); //去括号(一定要放在此处!!!)
a[++jj]=getss(l,r);
return jj; //取出单项式
}
nn b[100],c[100];
int nb=ys(l,mid-1,b);
int nc=ys(mid+1,r,c); //把两边的单项式取出来
if(cc[mid]=='+')
{
int na=nb+nc;
for(int i=1;i<=nb;i++) a[i]=b[i];
for(int j=1;j<=nc;j++) a[j+nb]=c[j];
return na; //加法
}
else if(cc[mid]=='-')
{
int na=nb+nc;
for(int i=1;i<=nb;i++) a[i]=b[i];
for(int j=1;j<=nc;j++) {a[j+nb]=c[j];a[j+nb].a[0]=-a[j+nb].a[0];}
return na; //减法(加上系数为负的后一半式子)
}
else
{
int na=nb*nc;
for(int i=1;i<=nb;i++)
for(int j=1;j<=nc;j++)
{
for(int k=1;k<=26;k++) a[i*nc-nc+j].a[k]=b[i].a[k]+c[j].a[k];
a[i*nc-nc+j].a[0]=b[i].a[0]*c[j].a[0]; //乘法(指数相加,系数相乘)
}
return na; }
}
inline int ccmp(nn a,nn b) {return strcmp(a.zz,b.zz)<0;} //排序(字典序)
int main()
{
freopen("xzz.in","r",stdin);
freopen("xzz.out","w",stdout);
scanf("%s",cc);
bool first=true;
int len=strlen(cc);
int tot=ys(0,len-1,z);
for(int i=1;i<=tot;i++)
for(int j=1;j<=26;j++)
for(int k=1;k<=z[i].a[j];k++)
z[i].zz[z[i].x++]=j+96; //把里面的a数组转为字符串(For example a[1]==1,a[3]==2,a[4]==1 zz="accd")
sort(z+1,z+tot+1,ccmp);
for(int i=1;i<=tot;i++)
if(strcmp(z[i].zz,z[i+1].zz)==0) z[i+1].a[0]+=z[i].a[0]; //若这一项与后一项为同类项,则把系数加给后一项
else
{
if((z[i+1].a[6]==1&&z[i+1].a[26]==1)||(z[i+1].a[4]==1&&z[i+1].a[6]==1&&z[i].a[4]==1&&z[i].a[5]==1)) swap(z[i+1],z[i]); //特判(emmm)
if(z[i].a[0]==0) continue; //系数为0
if(z[i].a[0]<0) printf("-"); //系数为负
else if(!first) printf("+"); //系数为正(第一项不输出'+')
first=false;
if(abs(z[i].a[0])!=1) printf("%d",abs(z[i].a[0])); //系数绝对值不唯一就输出
for(int j=1;j<=26;j++)
if(z[i].a[j])
{
printf("%c",j+96);
if(z[i].a[j]>1) printf("^%d",z[i].a[j]); //输出后面的字母(带'^'哦)
}
}
return 0;
}