题解

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define M 10007
typedef struct Node
{
    int n0, n1;
} Node;
Node node[2*N];
int p = 1;
stack<int> nStk;
stack<char> cStk;
int pri[128];
void initPri()
{
	pri['('] = 5; pri['*'] = 4; pri['+'] = 3; pri[')'] = 2;;
}
int main()
{
	initPri();
	int len, np, lp, rp;
	char c;
	string s;
	cin>>len;
	cin>>s;
	s += ')';
	for(int i = 0; i <= len; ++i)
	{
		if(s[i] != '(' && (i == 0 || s[i-1] != ')'))
		{
			np = p++;
			node[np].n0 = node[np].n1 = 1;
			nStk.push(np);
		}
		while(!(cStk.empty() || pri[s[i]] > pri[cStk.top()] || cStk.top() == '('))
		{
			np = p++;
			c = cStk.top(); cStk.pop();
			rp = nStk.top(); nStk.pop();
			lp = nStk.top(); nStk.pop();
			int l1 = node[lp].n1, l0=node[lp].n0, r1=node[rp].n1, r0=node[rp].n0;
			if(c == '+')
			{
				node[np].n0 = (l0 * r0) % M;
				node[np].n1 = (l0 * r1 + l1 * r0 + l1 * r1) % M;
			}
			else if(c == '*')
			{
				node[np].n0 = (l1 * r0 + l0 * r1 + l0 * r0) % M;
				node[np].n1 = (l1 * r1) % M;
			}
			nStk.push(np);
		}
		if(cStk.empty() == false && cStk.top() == '(' && s[i] == ')')
			cStk.pop();
		else
			cStk.push(s[i]);
	}
	cout<<node[nStk.top()].n0;
	return 0;
}