AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define mod 10007

struct node
{
int zero,one;
}k;
int l,len;
string s;
char c[200005];
map<char,int>level;
stack<node>st_num;
stack<char>st_op;

void pop_and_calc()
{
node k1=st_num.top();
st_num.pop();
node k2=st_num.top();
st_num.pop();
node k_new;
char op=st_op.top();
st_op.pop();

if(op=='+')
{
k_new.zero=k1.zero*k2.zero%mod;
k_new.one=(k1.zero*k2.one%mod+k1.one*k2.zero%mod+k1.one*k2.one%mod)%mod;
}
else if(op=='*')
{
k_new.zero=(k1.zero*k2.zero%mod+k1.zero*k2.one%mod+k1.one*k2.zero%mod)%mod;
k_new.one=k1.one*k2.one%mod;
}

st_num.push(k_new);
}

int main()
{
scanf("%d",&l);
cin>>s;
level['(']=0;
level['+']=1;
level['*']=2;
s="("+s;
s+=")";

for(int i=1;i<=l;i++)
{
if(s[i]=='(' || s[i]==')')
{
c[++len]=s[i];
continue;
}
if(s[i-1]!=')')
{
if(c[len]!='_')c[++len]='_';
}
c[++len]=s[i];
if(s[i+1]!='(')
{
if(c[len]!='_')c[++len]='_';
}
}

for(int i=1;i<=len;i++)
{
if(c[i]=='_')
{
k.zero=1;
k.one=1;
st_num.push(k);
}
else if(c[i]=='(')
{
st_op.push(c[i]);
}
else if(c[i]==')')
{
while(st_op.top()!='(')pop_and_calc();
st_op.pop();
}
else
{
while(1)
{
if(st_op.empty())
{
break;
}
else if(level[c[i]]<=level[st_op.top()])
{
pop_and_calc();
}
else
{
break;
}
}
st_op.push(c[i]);
}
}
while(!st_op.empty())pop_and_calc();

printf("%d\n",st_num.top().zero);
return 0;
}

1 条评论

  • 1

信息

ID
1808
难度
6
分类
(无)
标签
递交数
720
已通过
204
通过率
28%
被复制
9
上传者