题目描述


运算的优先级是：

1.先计算括号内的，再计算括号外的。
2.“× ”运算优先于“⊕”运算，即计算表达式时，先计算× 运算，再计算⊕运算。例如：计算表达式A⊕B × C时，先计算 B × C，其结果再与 A 做⊕运算。

现给定一个未完成的表达式，例如_+(_*_)，请你在横线处填入数字 0 或者 1 ，请问有多少种填法可以使得表达式的值为 0 。

输入描述:

共 2 行。
第1 行为一个整数 L ，表示给定的表达式中除去横线外的运算符和括号的个数。
第2 行为一个字符串包含 L 个字符，其中只包含’（’、’）’、’+’、’*’这 4 种字符，其中’（’、’）’是左右括号，’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。

输出描述:

共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对 10007 取模后的结果。

示例1

输入
4
+(*)
输出
3

备注:

对于 20% 的数据有 。
对于 50% 的数据有 。
对于 70% 的数据有 。
对于 100% 的数据有 。
对于 50% 的数据输入表达式中不含括号。

解答

本题难点在于：

1.有优先级

2.有括号

我们先分析一下

这是一道表达式计算的扩展题，对选手最基本的要求就是表达式计算。在一般的表达式计算中，存放结果的栈都是记录计算到某一步的结果，而在这道题中，结果只可能为2个（0或者1），且是知道的，而运算的数字是不一定的，所以在栈中只需存放算到0或者1时的方案数，最后输出到最后算出0的方案数即可。

算法实现

一、 首先粗略地说一下表达式计算的方法： 需要使用两个栈，一个存放结果，另一个存放符号。每次读入一个数据，就进入结果栈，如果是符号，则按以下方法： 1、 如果是左括号，就直接进栈； 2、 如果是右括号，就一直弹栈并加以计算，直到弹到左括号； 3、 如果是运算符，则弹栈，直到这个运算符的优先级大于符号栈栈顶的符号的优先级 或是左括号或栈空，然后将运算符进栈； 最后再将栈中残余的符号和结果一直弹到只剩一个结果，这个就是最后的结果。 二、 此题算法的框架整体上是和表达式计算相同的，有以下几个方面不同： 1、需要添加数字的地方应该满足不在右括号的后面或者左括号的前面 2、优先级：“*”的优先级比“+”高 3、运算方法，每一步计算为0或1的方法数：设两个步骤的运算结果经过每个符号到一个结果时，第一个运算结果算出0的方案数为t1,1的方案数为t2,第二个算出0的方案数为t3，算出1的方案数为t4，则有： 当符号是“⊕”时，得到0的方案数为t1*t3,1的方案数：t1*t4+t2*t3+t2*t4 当符号是“×”时，得到0的方案数为t1*t3+t1*t4+t2*t3,1的方案数：t2*t4 用一个栈记录下来即可

参考代码： 
#include<stdio.h>
const int M=10007,N=100005;
int n,i,u[N],v[N],top,k;
char c[N],sta[N],ans[2*N];
int main()
{
    //freopen("exp.in","r",stdin);
    //freopen("exp.out","w",stdout);
    scanf("%d\n%s",&n,c);
    ans[++k]='.';
    for(i=0;c[i];i++)
    {
        if(c[i]=='('||c[i]=='*')
           sta[++top]=c[i];
        if(c[i]=='+')
        {
            while(sta[top]=='*')
                ans[++k]=sta[top--];
            sta[++top]=c[i];
        }
        if(c[i]==')')
        {
            while(sta[top]!='(')
                ans[++k]=sta[top--];
            top--;
        }
        if(c[i]!='('&&c[i]!=')')
           ans[++k]='.';
    }
    while(top>0)
        ans[++k]=sta[top--];
    for(i=1;i<=k;i++)
    {
        if(ans[i]=='.')
        {
            u[++top]=1;
            v[top]=1;
        }
       if(ans[i]=='*')
        {
            top--;
            u[top]=(u[top+1]*v[top]+u[top]*v[top+1]+u[top]*u[top+1])%M;
            v[top]=v[top]*v[top+1]%M;
        }
        if(ans[i]=='+')
        {
            top--;
            v[top]=(u[top+1]*v[top]+u[top]*v[top+1]+v[top]*v[top+1])%M;
            u[top]=u[top]*u[top+1]%M;
        }
    }
    printf("%d",u[1]);
}


来源：蓝色如烟