65分RE求助代码怎么改
查看原帖
65分RE求助代码怎么改
500803
zzxzzxCCC楼主2022/11/13 23:28
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
const int N=20000050;
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+=s0[i];
        else if(s0[i]=='|'){
            while(topa&&(sta[topa]=='|'||sta[topa]=='&'))
			    s+=sta[topa--];
            sta[++topa]='|';
        }
        else if(s0[i]=='&'){
            while(topa&&sta[topa]=='&')
			    s+=sta[topa--];
            sta[++topa]='&';
        }
        else if(s0[i]=='(')
            sta[++topa]='(';
        else if(s0[i]==')'){
            while(topa&&sta[topa]!='(')
			    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 u){//中序遍历 
    if(!tree[u].leftchild)
	    return ;
    dfs(tree[u].leftchild);
    if(tree[tree[u].leftchild].root==0&&tree[u].oper=='&'){
	    sumyu++;
		return ;
	}
    if(tree[tree[u].leftchild].root==1&&tree[u].oper=='|'){
	    sumhuo++;
		return ;
	}
    dfs(tree[u].rightchild);
}
int main(){
    cin>>s0;
    change();
    build();
    dfs(cnt);
    printf("%d\n",tree[cnt].root);
    printf("%d %d",sumyu,sumhuo);
    return 0;
}

RE

2022/11/13 23:28
加载中...