简答题
偏难
#23605
表达式的值 【问题描述】 对于1位二进制变量定义两种运算: 运算的优先级是: 1. 先计算括号内的,再计算括号外的。 现给定一个未完成的表达式,例如 +( *…
表达式的值
【问题描述】
对于1位二进制变量定义两种运算:

运算的优先级是:
1. 先计算括号内的,再计算括号外的。

现给定一个未完成的表达式,例如 +( * ),请你在横线处填入数字0或者1,请问有多少种填法可以使得表达式的值为0。
【输入】
输入文件名为exp.in,共2行。
第1行为一个整数L,表示给定的表达式中除去横线外{的运算符和括号的个数。
第2行为一个字符串包含L个字符,其中只包含’(’、’)’、²+’、”*这4种字符,其中’ (’、’)’是左右括号,’+’、’*’分别表示前面定义的运算符“田”和“×”。这行字符按顺序 给出了给定表达式中除去变量外的运算符和括号。
【输出】
输出文件exp.out共1行。包含一个整数,即所有的方案数。 注意:这个数可能会很大, 请输出方案数对10007取模后的结果。
【输入输出样例1】

【输入输出样例说明】
给定的表达式包括横线字符之后为: +( * )
在横线位置填入(0、0、0)、(0、1、0)、(0、0、1)时,表达式的值均为0,所以共有3 种填法。
【数据范围】
对于20%的数据有O≤L≤10。
对于50%的数据有O≤L≤1,000。
对于70%的数据有O≤L≤10,000。
对于100%的数据有O≤L≤100,000。
对于50%的数据输入表达式中不含括号。
答案与解析
正确答案:<p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int MOD=10007;</p><p style="text-align: left;">int f[2][100005]; //每一位是0的可能性和是1的可能性 </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"> int len;</p><p style="text-align: left;"> string c,pol=".";</p><p style="text-align: left;"> cin>>len>>c;</p><p style="text-align: left;"> stack<char> sta;</p><p style="text-align: left;"> for(int i=0;i<len;i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(c[i]=='(' || c[i]=='*')</p><p style="text-align: left;"> sta.push(c[i]);</p><p style="text-align: left;"> if(c[i]=='+')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> while(!sta.empty() && sta.top()=='*')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> pol+=sta.top();</p><p style="text-align: left;"> sta.pop();</p><p style="text-align: left;"> }</p><p style="text-align: left;"> sta.push('+');</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(c[i]==')')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> while(sta.top()!='(')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> pol+=sta.top();</p><p style="text-align: left;"> sta.pop();</p><p style="text-align: left;"> }</p><p style="text-align: left;"> sta.pop();</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(c[i]!='(' && c[i]!=')')</p><p style="text-align: left;"> pol+='.';</p><p style="text-align: left;"> }</p><p style="text-align: left;"> while(!sta.empty())</p><p style="text-align: left;"> {</p><p style="text-align: left;"> pol+=sta.top();</p><p style="text-align: left;"> sta.pop();</p><p style="text-align: left;"> }</p><p style="text-align: left;"> int j=0;</p><p style="text-align: left;"> for(int i=0;i<(int)pol.length();i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(pol[i]=='.')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> j++;</p><p style="text-align: left;"> f[0][j]=1;</p><p style="text-align: left;"> f[1][j]=1;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(pol[i]=='*')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> j--;</p><p style="text-align: left;"> 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;</p><p style="text-align: left;"> f[1][j]=(f[1][j]*f[1][j+1])%MOD;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(pol[i]=='+')</p><p style="text-align: left;"> {</p><p style="text-align: left;"> j--;</p><p style="text-align: left;"> 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;</p><p style="text-align: left;"> f[0][j]=(f[0][j]*f[0][j+1])%MOD;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> cout<<f[0][j]<<endl; //f[0][1]</p><p style="text-align: left;"> return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。