记录

代码：

#include <bits/stdc++.h>
using namespace std;
string str;
int ad,od;
string sub(string ss,int b,int e)
{
    return ss.substr(b,e-b);
}
bool dp(string s)
{
    if(s[0]=='(' and s[s.length()-1]==')')
    {
        int c=0;
        for(int i=1;i<s.length()-1;i++)
        {
            if(s[i]==')')
            {
                c--;
            }
            if(s[i]=='(')
            {
                c++;
            }
            if(c<0)
            {
                c=1000000000000;
            }
        }
        if(c==0)
        {
            s=s.substr(1,s.length()-2);
        }
    }
    if(s=="1")
    {
        return 1;
    }
    else if(s=="0")
    {
        return 0;
    }
    int x=s.length()-1,p=0,c=0;
    while(x>0)
    {
        if(s[x]==')')
        {
            c++;
        }
        if(s[x]=='(')
        {
            c--;
        }
        if(s[x]=='&' and p==0 and c==0)
        {
            p=x;
        }
        if(s[x]=='|' and c==0)
        {
            break;
        }
        x--;
    }
    if(x!=0)
    {
        bool b=dp(sub(s,0,x));
        if(b==1)
        {
            ad++;
            return 1;
        }
        else
        {
            return dp(sub(s,x+1,s.length()));
        }
    }
    else
    {
        bool b=dp(sub(s,0,p));
        if(b==0)
        {
            od++;
            return 0;
        }
        else
        {
            return dp(sub(s,p+1,s.length()));
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>str;
    cout<<dp(str)<<endl;
    cout<<od<<' '<<ad;
    return 0;
}

递归 时间复杂度O（s log s——s^2）