#include<iostream>//通过递归去计算结果。方法：找出最低运算符的位置c，递归计算这个运算符两这的结果，然后根据运算符计算出结果。

#include<cstdio>//最后一组数据据基本是是括号嵌套。

#include<cstring>

#include<cstdlib>

struct node

{

int f0,f1;

};

char exp[100005];

int n,kh[100005],poi[50005];

int find(int x,int y)//返回最低运算符位置

{

int c=-1,p=0;

int i;

for (i=y;i>=x;i--)

{

switch (exp[i])

{

case '(':break;

case ')':i=kh[i];;break;

case '+':return i;

case '*':c=i;break;

}

}

return c;

}

node dp(int x,int y)

{

if (x>y)

{ node num;

num.f0=1;

num.f1=1;

return num;

}

int c=find(x,y);

if (c<0) return dp(x+1,y-1); //如果当前是括号

node left=dp(x,c-1),right=dp(c+1,y);

node ans;

if (exp[c]=='+')

{

ans.f0=(left.f0*right.f0)%10007;

ans.f1=(left.f1*right.f1+left.f0*right.f1+left.f1*right.f0)%10007;

}

else

{

ans.f0=(left.f0*right.f0+left.f0*right.f1+left.f1*right.f0)%10007;

ans.f1=(left.f1*right.f1)%10007;

}

return ans;

}

int main()

{

scanf("%d\n",&n);

int zz=0;

for(int i=1;i<=n;i++)

{

scanf("%c",&exp[i]);

if(exp[i]=='(')

{

zz++;

poi[zz]=i;

}

if(exp[i]==')')

{

kh[i]=poi[zz];

zz--;

}

}

node ans=dp(1,n);

printf("%d\n",ans.f0);

return 0;

}

怪事，我发现测评机最近老是出问题啊！！！

第一次 错误1组 无输出2组 超时1组

第二次 原封不动提交上去 居然AC了

貌似网上怎么也找不到2012年的测试数据

有解题思路么大哥。