记录编号	547765	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]表达式的值	最终得分	100
用户昵称	fmq03	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2019-12-13 21:02:02	内存使用	13.66 MiB

#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
#include<vector>
#define MO 10007
using namespace std;
int main(){
	freopen("exp.in","r",stdin);
	freopen("exp.out","w",stdout);
	int n;
	string str="";
	cin>>n;
	for(int i=1;i<=n;++i){
		char tmp;
		cin>>tmp;
		if((tmp=='*'||tmp=='+'||tmp==')')&&str[str.length()-1]!=')'){
			str+='0';	
		}
		str+=tmp;
	}
	if(str[str.length()-1]!=')')str+='0';
	stack<long>ope,sta1,sta0;
	for(int i=0;i<str.length();++i){
		char ch=str[i];
		if(ch=='0'){
			sta1.push(1);
			sta0.push(1);
		}else if(ope.empty()&&(ch=='*'||ch=='+')){
			ope.push(ch);
		}else if(ch=='('){
			ope.push(ch);
		}else if(ch==')'){
			while(ope.top()!='('){
				long a0,b0,a1,b1;
				a0=sta0.top();sta0.pop();
				a1=sta1.top();sta1.pop();
				b0=sta0.top();sta0.pop();
				b1=sta1.top();sta1.pop();
				char nowch=ope.top();ope.pop();
				if(nowch=='+'){
					long c1=a1*b1+a1*b0+a0*b1;
					long c0=a0*b0;
					sta1.push(c1%MO);
					sta0.push(c0%MO);
				}else if(nowch=='*'){
					long c1=a1*b1;
					long c0=a1*b0+a0*b1+a0*b0;
					sta1.push(c1%MO);
					sta0.push(c0%MO);
				}
			}
			ope.pop();
		}else{
			while((ope.empty()!=true && ch=='*' && ope.top()=='*') ||(ope.empty()!=true && ch=='+' && ope.top()!='(')){
				long a0,b0,a1,b1;
				a0=sta0.top();sta0.pop();
				a1=sta1.top();sta1.pop();
				b0=sta0.top();sta0.pop();
				b1=sta1.top();sta1.pop();
				char nowch=ope.top();ope.pop();
				if(nowch=='+'){
					long c1=a1*b1+a1*b0+a0*b1;
					long c0=a0*b0;
					sta1.push(c1%MO);
					sta0.push(c0%MO);
				}else if(nowch=='*'){
					long c1=a1*b1;
					long c0=a1*b0+a0*b1+a0*b0;
					sta1.push(c1%MO);
					sta0.push(c0%MO);
				}
			}
			ope.push(ch);
		}
	}
	while(!ope.empty()){
		long a0,b0,a1,b1;
			a0=sta0.top();sta0.pop();
			a1=sta1.top();sta1.pop();
			b0=sta0.top();sta0.pop();
			b1=sta1.top();sta1.pop();
			char nowch=ope.top();ope.pop();
			if(nowch=='+'){
				long c1=a1*b1+a1*b0+a0*b1;
				long c0=a0*b0;
				sta1.push(c1%MO);
				sta0.push(c0%MO);
			}else if(nowch=='*'){
				long c1=a1*b1;
				long c0=a1*b0+a0*b1+a0*b0;
				sta1.push(c1%MO);
				sta0.push(c0%MO);
			}
	}
	cout<<sta0.top()<<endl;
	return 0;
}