记录编号	324472	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]表达式的值	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2016-10-18 09:46:35	内存使用	2.85 MiB

#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
#define mod 10007
#define maxn 1000000
using namespace std;
char ch[maxn],s[maxn],p[maxn];
int m=0;
class poi{
public:
	int a0,a1;
	poi(){
		a0=1;
		a1=1;
	}
	poi operator + (const poi p)const{
		poi t;
		t.a0=(p.a0*a0)%mod;
		t.a1=(p.a1*a1+p.a1*a0+p.a0*a1)%mod;
		return t;
	}
	poi operator * (const poi p)const{
		poi t;
		t.a0=(p.a0*a0+p.a1*a0+p.a0*a1)%mod;
		t.a1=(p.a1*a1)%mod;
		return t;
	}
};
int main(){
	freopen("exp.in","r",stdin);
	freopen("exp.out","w",stdout);
	int n;
	scanf("%d",&n);
	scanf("%s",ch);
	ch[n]='=';
	int tot=0;
	for (int i=0;i<=n;i++){
		if (ch[i]=='('||s[tot-1]==')');
		else s[tot++]='_';
		s[tot++]=ch[i];
	}
	stack<char> mark;
	stack<poi> st;
	for (int i=0;i<=tot;i++){
		switch(s[i]){
			case '_':{
				p[m++]='_';
				continue;
			}
			case '(':{
				mark.push('(');
				continue;
			}
			case '*':{
				mark.push('*');
				continue;
			}
			case '+':{
				while(!mark.empty()){
					char t=mark.top();
					if (t=='(') break;
					p[m++]=t;
					mark.pop();
				}
				mark.push('+');
				continue;
			}
			case ')':{
				while(!mark.empty()){
					char t=mark.top();
					if (t=='('){
						mark.pop();
						break;
					}
					p[m++]=t;
					mark.pop();
				}
				continue;
			}
			case '=':{
				while(!mark.empty()){
					char t=mark.top();
					if (t=='(') {
						mark.pop();
						continue;
					}
					p[m++]=t;
					mark.pop();
				}
				continue;
			}
		}
	}
	for (int i=0;i<m;i++){
//		printf("%c",p[i]);
		switch(p[i]){
			case '_':{
//				num.push(p[i]);
				poi t;
				st.push(t);
				continue;
			}
			case '+':{
				poi t=st.top();
				st.pop();
				t=t+st.top();
				st.pop();
				st.push(t);
				continue;
			}
			case '*':{
				poi t=st.top();
				st.pop();
				t=t*st.top();
				st.pop();
				st.push(t);
				continue;
			}
		}
	}
	printf("%d",st.top().a0);
//	for () 
	return 0;
}