P1310 表达式的值

P1310 表达式的值

题解

1.假设有两个布尔变量 x , y 

   x0表示使得x=0的方案数

   x1表示使得x=1的方案数

   y0表示使得y=0的方案数

   y1表示使得y=1的方案数

| 按位或	& 按位与
0 0 -> 0	0 0 -> 0
0 1 -> 1	0 1 -> 0
1 0 -> 1	1 0 -> 0
1 1 -> 1	1 1 -> 1

then, 

x | y=0  方案数为 x0*y0

x | y=1  方案数为 x0*y1+x1*y0+x1*y1

x & y=0  方案数为  x0*y1+x1*y0+x0*y0  

x & y=1  方案数为  x1*y1

2.中缀转后缀规则

考虑用栈维护。

遍历中缀表达式：

1. 遇到数字，直接放入答案序列

2. 遇到左括号，入栈

3. 遇到右括号，把栈顶到上一个左括号的元素依次出栈并放入答案序列
4. 遇到乘号，入栈
5. 遇到加号，从栈顶开始弹出这段连续的乘号，并放入答案序列，最后加号入栈

6. 最后把栈里剩下的元素依次放入答案序列

代码

#include<bits/stdc++.h>

using namespace std;

const int mod=1e4+7;
const int maxn=1e5+5;
int n;
char zhong[maxn];  //输入的中序遍历 
stack<char>sta;    //栈 
string hou;        //转化的后缀表达式 
stack<int> zero,one;  //答案为0的方案数，答案为1的方案数 

int main()
{
    scanf("%d",&n);
    scanf("%s",zhong+1);  //下标从1开始 
    
    hou.push_back('n');   //后缀表达式里一开始要有一个未知数 
    
    //中缀转后缀 
    for(int i=1;i<=n;i++)
    {
        if(zhong[i]=='('||zhong[i]=='*')
           sta.push(zhong[i]);
        if(zhong[i]=='+')
        {
            while(!sta.empty()&&sta.top()=='*')
            {
                hou.push_back(sta.top());
                sta.pop(); 
            }
            sta.push(zhong[i]);
        }   
        if(zhong[i]==')')
        {
            while(sta.top()!='(')
            {
                hou.push_back(sta.top());
                sta.pop(); 
            }
            sta.pop();  //弹出'(' 
        }
        if(zhong[i]!='('&&zhong[i]!=')')
          hou.push_back('n');  //放入一个未知变量 
    } 
    
    //栈里面剩余的存入后缀 
    while(!sta.empty())
    {
        hou.push_back(sta.top());
        sta.pop(); 
    }
    
    //遍历后缀 
    for(int i=0;i<hou.size() ;i++)
    {
        char c=hou[i];
        
        if(c=='n')
        {
            zero.push(1);
            one.push(1);
        }
        else
        {
            int rone=one.top(),rzero=zero.top();
            one.pop();
            zero.pop();
            //rone->y1 , rzero->y0
            
            int lone=one.top(),lzero=zero.top();
            one.pop();
            zero.pop();
            //lone->x1 , lzero->x0
            
            if(c=='*')  
            {
                one.push(lone*rone%mod);
                zero.push((lone*rzero%mod+lzero*rone%mod+lzero*rzero%mod)%mod);
            }
            else
            {
                one.push((lone*rone%mod+lone*rzero%mod+lzero*rone%mod)%mod);
                zero.push(lzero*rzero%mod);
            }
        }
    }
    
    printf("%d",zero.top());  //输出答案 
    
    return 0;
}

Thanks

water-lift