- 表达式的值
- 2016-08-27 16:25:23 @
#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 条评论
-
NERvGear LV 8 @ 2016-10-03 14:38:27
// input code here
- 1
信息
- ID
- 1808
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 750
- 已通过
- 214
- 通过率
- 29%
- 被复制
- 14
- 上传者