题解

#include <bits/stdc++.h>
using namespace std;
const int MOD=10007;
int f[2][100005]; //每一位是0的可能性和是1的可能性
int main()
{
int len;
string c,pol=".";
cin>>len>>c;
stack<char> sta;
for(int i=0;i<len;i++)
{
if(c[i]'(' || c[i]'')
sta.push(c[i]);
if(c[i]'+')
{
while(!sta.empty() && sta.top()'')
{
pol+=sta.top();
sta.pop();
}
sta.push('+');
}
if(c[i]')')
{
while(sta.top()!='(')
{
pol+=sta.top();
sta.pop();
}
sta.pop();
}
if(c[i]!='(' && c[i]!=')')
pol+='.';
}
while(!sta.empty())
{
pol+=sta.top();
sta.pop();
}
int j=0;
for(int i=0;i<(int)pol.length();i++)
{
if(pol[i]'.')
{
j++;
f[0][j]=1;
f[1][j]=1;
}
if(pol[i]'*')
{
j--;
f[0][j]=(f[0][j+1]*f[1][j]+f[0][j]*f[1][j+1]+f[0][j]*f[0][j+1])%MOD;
f[1][j]=(f[1][j]*f[1][j+1])%MOD;
}
if(pol[i]'+')
{
j--;
f[1][j]=(f[0][j]*f[1][j+1]+f[0][j+1]*f[1][j]+f[1][j]*f[1][j+1])%MOD;
f[0][j]=(f[0][j]*f[0][j+1])%MOD;
}
}
cout<<f[0][j]<<endl; //f[0][1]
return 0;
}