简答题 偏难
#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 &lt;bits/stdc++.h&gt;</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&gt;&gt;len&gt;&gt;c;</p><p style="text-align: left;">    stack&lt;char&gt; sta;</p><p style="text-align: left;">    for(int i=0;i&lt;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() &amp;&amp; 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]!='(' &amp;&amp; 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&lt;(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&lt;&lt;f[0][j]&lt;&lt;endl;  //f[0][1]</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。