化简

中缀表达式 模拟

题面

给出一个表达式，其中包含有数字、未知数$x$、$+$、$-$、$*$和括号。把它化简成$a_0x^0+a_1x^1+a_2x^2+...+a_nx^n$的形式。系数模$10007$。

• $|S|\leq1000$

解析

显然直接模拟。

对于直接求中缀表达式的值：

• 维护一个数字栈和一个运算符栈
• 若当前字符为数字，直接插入栈（或融入栈顶）;
  若当前字符为运算符，且比栈顶运算优先级高（不能相等），直接插入;
  否则弹出栈顶，取数字栈顶两个数进行运算，再把结果塞回数字栈，直到满足条件为止。
• 若当前字符为左括号，直接插入;若为右括号，弹栈顶直到遇到左括号。

如果加上了未知数，就把数字栈变为多项式栈，用结构体储存所有项的系数，模拟一般多项式运算即可。复杂度上限$O(n*(\frac{n}{2})^2)$

听起来很简单是吧。然而我调了2h

• 每次运算后马上把系数取模，并变为正数，否则会炸$long\ long$
• 弹栈时记得把栈顶所有信息清$0$（插入时也可）
• 看下最高次项系数是否为$0$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=10007;
char s[1005],sta[1005];
int len,top,tot,id[1005];
struct dui
{
  ll x[1005],mx;
  il dui(){memset(x,0,sizeof(x));mx=0;}
}a[1005];
il void check(re ll &x) {while(x<0) x+=mod;if(x>=mod) x%=mod;}
il dui operator *(dui A,dui B)
{
  dui C;
  fp(i,0,A.mx)
    fp(j,0,B.mx)
    {
      C.x[i+j]+=A.x[i]*B.x[j];
      check(C.x[i+j]);
    }
  C.mx=A.mx+B.mx;while(C.x[C.mx]==0&&C.mx) --C.mx;
  return C;
}
il dui operator +(dui A,dui B)
{
  dui C;
  fp(i,0,max(A.mx,B.mx))
    {
    C.x[i]=A.x[i]+B.x[i];
    check(C.x[i]);
    }
  C.mx=max(A.mx,B.mx);while(C.x[C.mx]==0&&C.mx) --C.mx;
  return C;
}
il dui operator -(dui A,dui B)
{
  dui C;
  fp(i,0,max(A.mx,B.mx))
    {
    C.x[i]=A.x[i]-B.x[i];
    check(C.x[i]);
    }
  C.mx=max(A.mx,B.mx);while(C.x[C.mx]==0&&C.mx) --C.mx;
  return C;
}
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il int check(re char x,re char y)
{
  if(x=='(') return 1;if(x==')') return 0;
  return id[x]>id[y];
}
il void calc(re dui &x,re dui y,re char p)
{
  if(p=='+') x=x+y;
  if(p=='-') x=x-y;
  if(p=='*') x=x*y;
}
int main()
{
  freopen("simplify.in","r",stdin);
  freopen("simplify.out","w",stdout);
  scanf("%s",s+1);len=strlen(s+1);s[++len]='#';
  id['+']=id['-']=2;id['*']=3;id['#']=-1;id['?']=-2;sta[0]='?';
  fp(i,1,len)
    {
      if(s[i]>='0'&&s[i]<='9')
    {
      if(s[i-1]>='0'&&s[i-1]<='9') a[tot].x[0]=a[tot].x[0]*10+s[i]-'0';
      else a[++tot].mx=0,memset(a[tot].x,0,sizeof(a[tot].x)),a[tot].x[0]=s[i]-'0';
    }
      else if(s[i]=='x') memset(a[++tot].x,0,sizeof(a[tot].x)),a[tot].mx=1,a[tot].x[1]=1;
      else
    {
      if(check(s[i],sta[top])) sta[++top]=s[i];
      else
        {
          if(s[i]==')')
        {
          while(sta[top]!='(') {
            calc(a[tot-1],a[tot],sta[top]);--tot;--top;}
        --top;
        }
          else
        {
          while(!check(s[i],sta[top])) {
            calc(a[tot-1],a[tot],sta[top]);--tot;--top;
          }
          sta[++top]=s[i];
        }
        }
    }
    }
  printf("%lld\n",a[1].mx);
  fp(i,0,a[1].mx) printf("%lld\n",a[1].x[i]%mod);
  fclose(stdin);
  fclose(stdout);
  return 0;
}