洛谷 P1310 NOIP2011普及组 表达式的值 题解【DP】【字符串】【栈】

点击量：168

   普及组的题也会很毒瘤啊……

目录

题目描述

对于 1 位二进制变量定义两种运算：
运算符 运算规则
⊕
0⊕0=0
0⊕1=1
1⊕0=1
1⊕1=1
×
0 × 0=0
0 × 1=0
1 × 0=0
1 × 1=1

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

2. “×”运算优先于“⊕”运算，即计算表达式时，先计算×运算，再计算⊕运算。
例如：计算表达式A⊕B × C 时，先计算B × C，其结果再与A 做⊕运算。
现给定一个未完成的表达式，例如_+(_*_)，请你在横线处填入数字0 或者1，请有多少种填法可以使得表达式的值为0。

输入输出格式

输入格式：

共 2 行。

 

第 1 行为一个整数L，表示给定的表达式中除去横线外的运算符和括号的个数。

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

 

输出格式：

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

 

输入输出样例

输入样例#1：

4

+(*)

输出样例#1：

3

说明

【输入输出样例说明】

给定的表达式包括横线字符之后为：_+(_*_)

 

在横线位置填入(0 、0 、0) 、(0 、1 、0) 、(0 、0 、1) 时，表达式的值均为0 ，所以共有3种填法。

对于 20%的数据有0 ≤L≤ 10。

对于 50%的数据有0 ≤L≤ 1,000。

对于 70%的数据有0 ≤L≤ 10,000。

对于 100%的数据有0 ≤L≤ 100,000。

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

   其实如果理解清题意，这个DP/递推也是很好想的，不过这个题难就难在处理字符串和括号上。

   在一串表达式中，空格初始值为0和1各有一种情况，即DP初始值为v[0]=1,v[1]=1，接着如果是_+_，那么1可以由0⊕1，1⊕0（分别是两种），1⊕1的情况推过来，我们假设这两块空格都是初始状态，那么把这个式子合并成一个空格，继续转移，此时v[0]=1,v[1]=3。

   既然表达式中有括号，那么我们就应该用栈来做括号匹配的工作。因为括号的优先级大于乘法大于加法，所以我们把数和数后面的操作符（数后面的操作符要么是+要么是×或者是字符串结尾’\0’，下面给出证明）放在一个结构体中放入栈内。

   证明：因为不会出现省略×，即1(1+0)，所以任何数后面都不会有‘(’。

   如果是左括号，我们直接把它放入栈中，继续读入，因为它在数学运算中左边不能有数字。

   如果是右括号，我们就要进行从栈顶开始的括号匹配，将右括号右边的运算符（一定是运算符）存起来放在结构体里。此时的运算符只有+和×，我们只要按顺序进行就可以了，匹配的同时做递推。同时匹配到左括号时停止，并把存的运算符加给当前的结果。

   当我们检测到栈中次顶元素所带的操作符是×号，我们就要立即进行运算。因为×比+优先级高，但是如果出现×(+)，就会在上一步中跟下去着运算，等到退栈时会回来。而(+)×这种情况是不会存在的，因为前面匹配到完整的括号一定会消掉。

   当字符串匹配完后，结果可能是(……)或……，而其中只有加法（乘法被处理完了），我们就无脑匹配，特判最后一个是不是‘(’就可以了。

   剧毒的普及组题啊。。。

Code:

#include<cstdio>
#include<cstring>

char c[200000];
struct node
{
    int v[2];
    char op;
    node()
    {
        v[0]=1;
        v[1]=1;
    }
};
node s[200000];
int top=0;
int cnt=0;
int main()
{
    //freopen("testdata.in","r",stdin);
    int n;
    scanf("%d",&n);
    scanf("%s",c);
    int ans=0;
    node p,q;
    for(int i=0;i<=n;i++)
    {
        p.op=c[i];
        p.v[0]=1;
        p.v[1]=1;
        s[++top]=p;
        if(p.op=='(')
            continue;
        if(s[top-1].op=='*')
        {
            p=s[top--];
            q=s[top--];
            node t;
            t.op=p.op;
            t.v[0]=p.v[0]*q.v[0]+p.v[0]*q.v[1]+p.v[1]*q.v[0];
            t.v[1]=p.v[1]*q.v[1];
            t.v[0]%=10007;
            t.v[1]%=10007;
            s[++top]=t;
        }
        while(p.op==')')
        {
            s[top].op=c[++i];
            while(s[top-1].op!='(')//一定只剩加法?
            {
                p=s[top--];
                q=s[top--];
                node t;
                t.op=p.op;
                t.v[0]=p.v[0]*q.v[0];
                t.v[1]=p.v[0]*q.v[1]+p.v[1]*q.v[0]+p.v[1]*q.v[1];
                t.v[0]%=10007;
                t.v[1]%=10007;
                s[++top]=t;
            }
            p=s[top--];
            s[top]=p;
            if(s[top-1].op=='*')
            {
                p=s[top--];
                q=s[top--];
                node t;
                t.op=p.op;
                t.v[0]=p.v[0]*q.v[0]+p.v[0]*q.v[1]+p.v[1]*q.v[0];
                t.v[1]=p.v[1]*q.v[1];
                t.v[0]%=10007;
                t.v[1]%=10007;
                s[++top]=t;
            }
        }//可能还有乘法
    }
    int k=(s[1].op=='(')+1;
    while(top>k)
    {
        p=s[top--];
        q=s[top--];
        node t;
        t.op=p.op;
        t.v[0]=p.v[0]*q.v[0];
        t.v[1]=p.v[0]*q.v[1]+p.v[1]*q.v[0]+p.v[1]*q.v[1];
        t.v[0]%=10007;
        t.v[1]%=10007;
        s[++top]=t;
    }
    printf("%d\n",s[k].v[0]);
    return 0;
}