题解：#10 化简

思路

注意到 $s$ 的长度不超过 $1000$，所以最高次项次数不会超过 $505$，考虑直接模拟。

注意到直接模拟是困难的，所以考虑先把原字符串修改为后缀表达式以去除括号和运算符优先级，方便模拟。

对于转后缀表达式，可以用两个栈来做：从前向后遍历原字符串，每次遇到数字就将其放入第二个栈中，否则如果不是右括号（即 +，-，*，(），不断弹出第一个栈顶的元素并放入第二个栈中直到栈顶运算符的优先级（见代码）小于于该运算符；如果是右括号，则不断弹出第个栈顶元素放入第二个栈中直到栈顶元素为左括号，并弹出左括号，最后将第二个栈中的元素倒序一下就是转完的后缀表达式，另外，因为第二个栈不需要中途弹出，所以可以用队列代替，方便后续转为字符串。（转后缀表达式时不要忘记顺便加上空格方便后续模拟）

模拟时可以把每个元素都当做多项式来看待，运算就按照多项式运算来就可以。

对于后缀表达式的运算，从前往后遍历，每次遍历到非运算符就放入栈中，遍历到运算符就将栈顶两个元素取出，运算后再放入栈中，直到遍历完整个字符串，栈中剩下的元素就是最终答案。

（码风丑陋，勿喷）

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e4+7;
string s;
int cnt=0,cnt1[1005]={0};
int k[1005][1005];
stack<int >stp;
void j(int x,int y,int z){
	int sz=max(cnt1[x],cnt1[y]);
	for(int i=0;i<=sz;i++){
		k[z][i]=(k[x][i]+k[y][i]+mod)%mod;
		if(i==sz&&k[z][i]==0)sz--;
	}
	cnt1[z]=sz;
}
void jn(int x,int y,int z){
	int sz=max(cnt1[x],cnt1[y]);
	for(int i=sz;i>=0;i--){
		k[z][i]=(k[x][i]-k[y][i]+mod)%mod;
		if(i==sz&&k[z][i]==0)sz--;
	}
	cnt1[z]=sz;
}
void c(int x,int y,int z){
	int sz=cnt1[x]+cnt1[y];
	for(int i=0;i<=cnt1[x];i++){
		for(int j=0;j<=cnt1[y];j++){
			k[z][i+j]+=(k[x][i]*k[y][j]+mod);
			k[z][i+j]%=mod;
		}
	}
	while(!k[z][sz])sz--;
	cnt1[z]=sz;
}
void solve(){
	int nw=0,szz=s.size();
	while(nw<szz){
		while(nw<szz&&(!((s[nw]<='9'&&s[nw]>='0')||s[nw]=='x'||s[nw]=='+'||s[nw]=='-'||s[nw]=='*')))nw++;
		if(nw>=szz)break;
		if(s[nw]=='+'){
			int p1=stp.top();
			stp.pop();
			int p2=stp.top();
			stp.pop();
			j(p2,p1,++cnt);
			stp.push(cnt);
			nw++;
			continue;
		}
		else if(s[nw]=='-'){
			int p1=stp.top();
			stp.pop();
			int p2=stp.top();
			stp.pop();
			jn(p2,p1,++cnt);
			stp.push(cnt);
			nw++;
			continue;
		}
		else if(s[nw]=='*'){
			int p1=stp.top();
			stp.pop();
			int p2=stp.top();
			stp.pop();
			c(p2,p1,++cnt);
			stp.push(cnt);
			nw++;
			continue;
		}
		cnt++;
		while(nw<szz&&((s[nw]<='9'&&s[nw]>='0')||s[nw]=='x')){
			if(s[nw]=='x'){
				k[cnt][1]=1;
				cnt1[cnt]=1;
			}
			else {
				k[cnt][0]=(k[cnt][0]<<3)+(k[cnt][0]<<1);
				k[cnt][0]+=s[nw]-'0';
			}
			nw++;
		}
		stp.push(cnt);
	}
	int pans=stp.top(),ans=0;
	for(int i=0;i<=504;i++){
		if(k[pans][i]!=0)ans=i;
	}
	printf("%d\n",ans);
	for(int i=0;i<=ans;i++){
		printf("%d\n",k[pans][i]);
	}
}
string s1;
stack<char>st1;
queue<char>st2;
int mp[200];
int main(){
	cin>>s1;
	mp['+']=1;
	mp['-']=1;
	mp['*']=2;
	mp['(']=-1;
	if(s1[0]=='-')s1='0'+s1;
	int sz0=s1.size();
	bool f=0;
	for(int i=0;i<sz0;i++){
		if((s1[i]>='0'&&s1[i]<='9')||s1[i]=='x'){
			if(f==0){
				st2.push(' ');
				f=1;
			}
			st2.push(s1[i]);
		}
		else{
			f=0;
			if(st1.empty()||st1.top()=='('||s1[i]=='('){
				st1.push(s1[i]);
			}
			else if(s1[i]==')'){
				while(st1.top()!='('){
					st2.push(' ');
					st2.push(st1.top());
					st1.pop();
				}
				st1.pop();
			}
			else{
				while(!st1.empty()&&mp[st1.top()]>=mp[s1[i]]){
					st2.push(' ');
					st2.push(st1.top());
					st1.pop();
				}
				st1.push(s1[i]);
			}
		}
	} 
	while(!st1.empty()){
		st2.push(' ');
		st2.push(st1.top());
		st1.pop();
	}
	while(!st2.empty()){
		s+=st2.front();
		st2.pop();
	}
	solve();
	return 0;
}