C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 828K, 提交时间: 2019-11-12 15:45:43

#include<cstdio>

const int M = 10007,N = 100005;
int n,i,u[N],v[N],top,k;
char c[N],sta[N],ans[2*N];

int main()
{
	scanf("%d\n%s",&n,c);
	ans[++k] = '.';
	for(int i=0;c[i];i++)
	{
		if(c[i]=='('||c[i]=='*')
			sta[++top] = c[i];
		if(c[i]=='+')
		{
			while(sta[top]=='*')
				ans[++k] = sta[top--];
			sta[++top] = c[i];
		}
		if(c[i]==')')
		{
			while(sta[top]!='(')
				ans[++k] = sta[top--];
			top--;
		}
		if(c[i]!='('&&c[i]!=')')
			ans[++k] = '.';
	}
	while(top>0)
		ans[++k] = sta[top--];
	for(i=1;i<=k;i++)
	{
		if(ans[i]=='.')
		{
			u[++top] = 1;
			v[top] = 1;
		}
		if(ans[i]=='*')
		{
			top--;
			u[top] = (u[top+1]*v[top]+u[top]*v[top+1]+u[top]*u[top+1])%M;
			v[top] = v[top]*v[top+1]%M;
		}
		if(ans[i]=='+')
		{
			top--;
			v[top] = (u[top+1]*v[top]+u[top]*v[top+1]+v[top]*v[top+1])%M;
			u[top] = u[top]*u[top+1]%M;
		}
	}
	printf("%d\n",u[1]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 760K, 提交时间: 2020-10-07 16:15:46

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=10007;
stack<char> s;
char str[N];
struct node{
	int l,r;
}ans[N];
int t=1;

void fun(char ch,node &a,node &b){
	if(ch=='+'){
		a.r=(a.r*(b.l+b.r)+a.l*b.r)%mod;
		a.l=a.l*b.l%mod;
	}
	else{
		a.l=(a.l*(b.l+b.r)+a.r*b.l)%mod;
		a.r=a.r*b.r%mod;
	}
	return ;
}
int main(){
	int n,i;
	cin>>n>>str;
	str[n]=')';ans[1].l=ans[1].r=1;s.push('(');
	for(i=0;i<=n;i++)
	{
		if(str[i]=='(')
			s.push('(');
		else if(str[i]==')'){
			for(;s.top()!='(';s.pop(),t--)
				fun(s.top(),ans[t-1],ans[t]);
			s.pop();
		}
		else{
			for(;s.top()<=str[i]&&s.top()!='(';s.pop(),t--){
				fun(s.top(),ans[t-1],ans[t]);
			}
			s.push(str[i]);
			ans[++t].l=1;
			ans[t].r=1;
		}
	}
	cout<<ans[1].l<<endl;
	return 0;
}