自动搬运

查看原文

来自洛谷，原作者为

	star_magic_young 绽放吧,Freesia~

搬运于2025-08-24 21:37:02，当前版本为作者最后更新于2018-01-08 22:43:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}