求助
查看原帖
求助
726902
bcbgszyzh楼主2024/10/24 15:20

RE求助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXV=1e6+10;
struct node{
	char v;
	int l,r;
}; 
vector<node>g(MAXV);
int build(string sl){//建表达式树 
	int last=1;
	stack<int>st;
	for(int i=0;i<sl.size();++i){
		if(sl[i]=='0'||sl[i]=='1'){//是数字,放进表达式树 
			g[last].v=sl[i];
			st.push(last);
			++last;
		}
		if(sl[i]=='&'||sl[i]=='|'){// 是 符 号 , 处 理 
			int o2=st.top();
			st.pop();
			int o1=st.top();
			st.pop();
			g[last].l=o1,g[last].r=o2;g[last].v=sl[i]; 
			st.push(last);
			++last; 
		}
	}
	return st.top();
}
int dfs(int root,int &a,int &b){//dfs
	if(g[root].l==0&&g[root].r==0){//是叶子节点
		return g[root].v-'0'; 
	}
	int left=dfs(g[root].l,a,b);
	int ret=-1;
	if(g[root].v=='&'){//是& 
		if(left=0){
			++a,ret=0;
		}else{
			ret=dfs(g[root].r,a,b);
		}
	}else{
		if(g[root].v=='|'){//是| 
			if(left==1){
				++b,ret=1;
			}else{
				ret=dfs(g[root].r,a,b);
			}
		}
	}
	return ret;
}
string m2l(string s){//m2l 是中缀转后缀的函数 
	string res;
	stack<char>st;
	for(int i=0;i<s.size();++i){
		char c=s[i];
		switch(c){//遍历 
			case '0':
			case '1':
				res+=c;
				break;
			case '(':
				st.push(c);
				break;
			case ')':
				while(st.top()!='('){//把括号内的东西加进去 
					res+=st.top();
					st.pop();
				}
				st.push('&');
				break;
			case '&':
				while(st.size()>0&&st.top()!='|'&&st.top()!='('){
					res+=st.top();
					st.pop();
				}
				st.push('&');
				break;
			case '|':
				while(st.size()>0&&st.top()!='('){
					res+=st.top();
					st.pop();
				}
				st.push('|');
				break;
			default:
				puts("error1");
		}
	}
	while(st.size()>0){
		res+=st.top();st.pop();
	}
	return res;
} 
int main(){
	string s,sl;
	cin>>s;
	sl=m2l(s);
	int ro=build(sl); 
	int x=0,y=0;
	printf("%d\n",dfs(ro,x,y));
	printf("%d %d",x,y);
	return 0;
} 
2024/10/24 15:20
加载中...