50分求助
查看原帖
50分求助
500803
zzxzzxCCC楼主2022/11/11 22:43
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
struct Tree{
    int root,leftchild,rightchild;
    char oper;
}tree[N];
string s0,s;
char sta[N],topa;
int root,i,cnt,sumyu,sumhuo,stb[N],topb;
void change(){//中缀转后缀 
    for(int i=0;i<s0.size();i++){
        if(s0[i]=='0'||s0[i]=='1')
            s=s+s0[i];
        else if(s0[i]=='|'){
            while(topa>=0&&(sta[topa]=='|'||sta[topa]=='&'))
                s=s+sta[topa--];
            sta[++topa]='|';
        }
        else if(s0[i]=='&'){
            while(topa>=0&&sta[topa]=='&')
                s=s+sta[topa--];
            sta[++topa]='&';
        }
        else if(s0[i]=='(')
            sta[++topa]='(';
        else if(s0[i]==')'){
            while(topa>=0&&sta[topa]!='(')
                s=s+sta[topa--];
            topa--;
        }
    }
    while(topa)
        s+=sta[topa--];
}
void build(){//生成表达式树 
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'||s[i]=='1'){
            tree[++cnt].root=(int)(s[i]-'0');
            stb[++topb]=cnt;
        }
        else if(s[i]=='|'){
            tree[++cnt].rightchild=stb[topb--];
            tree[cnt].leftchild=stb[topb--];
            tree[cnt].root=tree[tree[cnt].leftchild].root|tree[tree[cnt].rightchild].root;
            tree[cnt].oper=s[i];
            stb[++topb]=cnt;
        }
        else if(s[i]=='&'){
            tree[++cnt].rightchild=stb[topb--];
            tree[cnt].leftchild=stb[topb--];
            tree[cnt].root=tree[tree[cnt].leftchild].root&tree[tree[cnt].rightchild].root;
            tree[cnt].oper=s[i];
            stb[++topb]=cnt;
        }
    }
}
void dfs(int x){
    if(!tree[x].leftchild)
        return ;
    dfs(tree[x].leftchild);
    if(tree[tree[x].leftchild].root==0&&tree[x].oper=='&'){
        sumyu++;
        return ;
    }
    if(tree[tree[x].leftchild].root==1&&tree[x].oper=='|'){
        sumhuo++;
        return ;
    }
    dfs(tree[x].rightchild);
}
int main(){
    cin>>s0;
    change();
    build();
    dfs(cnt);
    printf("%d\n",tree[cnt].root);
    printf("%d %d",sumyu,sumhuo);
    return 0;
}
2022/11/11 22:43
加载中...