20分求调(建表达式树)
查看原帖
20分求调(建表达式树)
1235109
wangyvting01楼主2024/10/7 16:02
#include<bits/stdc++.h>
using namespace std;
string s;
int ans1,ans2;
//建树
//中序遍历这颗树 

struct node{
	char id,x;//当前节点的字符 
	int l,r,f;//子节点 
}tree[1000010]; 

node num[2000010],str[2000010];
int t1,t2;
void num_push(node v){
	num[++t1]=v;
}
void str_push(node v){
	str[++t2]=v;
}
void num_pop(){
	--t1;
}
void str_pop(){
	--t2;
}
bool num_empty(){
	return t1==0;
}
bool str_empty(){
	return t2==0;
}
node num_top(){
	return num[t1];
}
node str_top(){
	return str[t2];
}

char g(char a,char b,char q){
	if(q=='&'){
		if(a=='1'&&b=='1'){
			return '1';
		}else{
			return '0';
		}
	}else{
		if(a=='0'&&b=='0'){
			return '0';
		}else{
			return '1';
		}
	}
}

char dfs(int rot){
	if(tree[rot].l==-1&&tree[rot].r==-1){//是叶子结点 
		return tree[rot].id;
	}
	char x,y;
	x=dfs(tree[rot].l);
	if(x=='1'&&tree[rot].id=='|'){
		ans2++;
		return '1';
	}
	if(x=='0'&&tree[rot].id=='&'){
		ans1++;
		return '0';
	}
	y=dfs(tree[rot].r);
	return g(x,y,tree[rot].id);
}

int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	cin>>s;
	for(int i=0;i<s.size();i++){
		tree[i].id=s[i];
		tree[i].x=i;
		tree[i].l=-1;
		tree[i].r=-1;
		tree[i].f=i;
	}
	//-------表达式求值---------- 
	for(int i=0;i<s.size();i++){
		if(tree[i].id=='0'||tree[i].id=='1'){//数字直接入 
			num_push(tree[i]); 
		}else{
			if(str_empty()||(((tree[i].id=='&' && str_top().id=='|')||str_top().id=='(')||tree[i].id=='(')){
				//空,优先级高,(直接入
				str_push(tree[i]); 
			}else{
				if(tree[i].id==')'){
					while(str_top().id!='('){
						node now1,now2,now3;
						now1=num_top();
						num_pop();
						now2=num_top();
						num_pop();
						now3=str_top();
						str_pop();
						tree[now3.x].l=now2.x;
						tree[now3.x].r=now1.x;
						tree[now2.x].f=now3.x;
						tree[now1.x].f=now3.x;
						num_push(node{g(now1.id,now2.id,now3.id),now3.x,tree[now3.x].l,tree[now3.x].r,tree[now3.x].f});
					}
					str_pop();
				}else if((tree[i].id=='|'&&str_top().id=='&')||(tree[i].id==str_top().id)){
					node now1,now2,now3;
					now1=num_top();
					num_pop();
					now2=num_top();
					num_pop();
					now3=str_top();
					str_pop();
					tree[now3.x].l=now2.x;
					tree[now3.x].r=now1.x;
					tree[now2.x].f=now3.x;
					tree[now1.x].f=now3.x;
					num_push(node{g(now1.id,now2.id,now3.id),now3.x,tree[now3.x].l,tree[now3.x].r,tree[now3.x].f});
					str_push(tree[i]);
				}
			}
		}
	}
	while(!str_empty()){
		node now1,now2,now3;
		now1=num_top();
		num_pop();
		now2=num_top();
		num_pop();
		now3=str_top();
		str_pop();
		tree[now3.x].l=now2.x;
		tree[now3.x].r=now1.x;
		tree[now2.x].f=now3.x;
		tree[now1.x].f=now3.x;
		num_push(node{g(now1.id,now2.id,now3.id),now3.x,tree[now3.x].l,tree[now3.x].r,tree[now3.x].f});
	}
	//---------表达式求值--------- 
	cout<<num_top().id<<"\n";
	int root;
	for(int i=0;i<s.size();i++){
		if(s[i]!=')'&&s[i]!='('&&tree[i].f==i){
			root=i;
			break;
		}
	}
	dfs(root);
	cout<<ans1<<" "<<ans2<<"\n";
	return 0;
} 
2024/10/7 16:02
加载中...