https://www.zybuluo.com/ysner/note/1238615
题面
给出一个表达式，其中包含有数字、未知数(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
",a[1].mx);
fp(i,0,a[1].mx) printf("%lld
",a[1].x[i]%mod);
fclose(stdin);
fclose(stdout);
return 0;
}