记录编号	324544	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]表达式的值	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.064 s
提交时间	2016-10-18 13:28:50	内存使用	0.79 MiB

#include<cstdio>
#include<stack>
#define file(x) "exp."#x
const int LEN=3e5+10,M=10007;
char s[LEN],s2[LEN];
int n,sz;
struct NODE{int a[2];NODE(int x,int y){a[0]=x,a[1]=y;}};
std::stack<NODE> st;
NODE gtop(){
	if(st.empty()) return NODE(1,1);
	else {
		NODE t=st.top();
		st.pop();
		return t;
	}
}
void toattr(){
	std::stack<char> st;
	for(int i=1;i<=n;i++){
		switch(s[i]){
			case '+':
				while(!st.empty()&&st.top()!='('){
					s2[++sz]=st.top();
					st.pop();
				}
				st.push(s[i]);
				break;
			case '*':
				while(!st.empty()&&st.top()!='('&&st.top()=='*'){
					s2[++sz]=st.top();
					st.pop();
				}
				st.push(s[i]);
				break;
			case ')':
				while(!st.empty()&&st.top()!='('){
					s2[++sz]=st.top();
					st.pop();
				}
				if(!st.empty()&&st.top()=='(') st.pop();
				break;
			case '(':st.push(s[i]);break;
			case '_':s2[++sz]='_';break;
		}
	}
	while(!st.empty()) s2[++sz]=st.top(),st.pop();
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++){
		char ch;
		scanf("%c",&ch);
		if(ch=='*'||ch=='+'){
			if(!sz||(s[sz]!=')'&&s[sz]!='_')) s[++sz]='_';
		}
		else if(ch==')'&&(s[sz]=='*'||s[sz]=='+')) s[++sz]='_';
		s[++sz]=ch;
	}
	if(s[sz]=='+'||s[sz]=='*') s[++sz]='_';
	n=sz;
	sz=0;
	toattr();
	//printf("%s",s2+1);
	for(int i=1;i<=sz;i++) {
		if(s2[i]=='+'){
			NODE x=gtop(),y=gtop();
			int o=x.a[1]*y.a[1]%M+x.a[1]*y.a[0]%M+x.a[0]*y.a[1]%M;
			int z=x.a[0]*y.a[0]%M;
			st.push(NODE(z%M,o%M));
		}
		else if(s2[i]=='*'){
			NODE x=gtop(),y=gtop();
			int o=x.a[1]*y.a[1]%M;
			int z=x.a[0]*y.a[0]%M+x.a[1]*y.a[0]%M+x.a[0]*y.a[1]%M;
			st.push(NODE(z%M,o%M));
		}
		else st.push(NODE(1,1));
	}
	NODE u=gtop();
	printf("%d",u.a[0]);
}