[CSP-J 2022] 逻辑表达式 (中缀表达式转后缀表达式 ， 后缀表达式建表达式树)_csp-j前中后缀表达式精讲

思路：

先中缀转后缀 ，然后后缀建表达式树 ， 最后中序遍历树 计算短路和表达式结果；

1. 中缀转后缀

需要一个 后缀序列 和一个 符号栈
中缀转后缀

1. 栈为空 或者 左括号 直接进符号栈 遇到数字直接进答案序列
2. 遇到右括号一直出栈到左括号 ， 左括号不进答案序列
3. 遇到其他符号比较优先级 ， 直到栈顶优先级比自己低为止 ， 左括号不出栈

void change(){
	int len = s.size();
	for(int i=0;i<len;i++){
		if(isdigit(s[i])) ve.push_back(s[i]);//数字直接进答案序列
		else if(st.empty() || s[i] == '(')  st.push(s[i]);//栈为空 和 左括号直接进栈
		else if(s[i] == ')'){
			while(st.top() != '(') ve.push_back(st.top()) , st.pop();
			st.pop();//左括号出栈
		}else if(s[i] == '&'){
			while(!st.empty() && st.top() == '&')  ve.push_back(st.top()) , st.pop(); st.push(s[i]);//&入栈 ， 栈顶不能是&
		}else{
			while(!st.empty() && st.top() == '&' || !st.empty() && st.top() == '|')  ve.push_back(st.top()) , st.pop(); st.push(s[i]);
		}// | 入栈 栈顶不能是 | 或者 &	
	}
	
	while(!st.empty()) ve.push_back(st.top()) , st.pop();//全部进入答案序列
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 后缀表达式建表达式树

需要一个节点栈来存树的节点

遍历后缀表达式序列 ， 遇到数字就建立一个叶节点把序号存入栈中 ， 遇到运算符号从栈中弹出两个节点 ，让运算符号作为这两个节点的父节点 ， 然后把合成的新树存进栈中。

1. 最后一个序号一定是树根的序号
2. 注意先从栈中取出来的节点是新节点的右子树，后取出来的是左子树

void build(){
	stack<int>sts;
	for(auto k : ve){
		if(k == '0' || k == '1') a[++cnt] = {k,-1,-1} , sts.push(cnt) ;
		else{
			int r = sts.top();sts.pop() , l = sts.top();sts.pop();
			a[++cnt] = {k,l,r};sts.push(cnt);
		}
	}
}
1
2
3
4
5
6
7
8
9
10

3. 中序遍历树计算结果

对于每一颗子树 ， 先计算左子树的结果，如果出现 “1 |” 或者是 “0 &” 的情况则不去访问右子树 ， 累加短路的答案 , 如果未出现短路 ，那么这颗子树的计算值一定是右子树的值 ， 因为 “0 | x == x”
“1 & x == x”

int dfs(int v){
	
	if(a[v].c == '1' || a[v].c == '0') return a[v].c - '0';
	int now = dfs(a[v].l); //先去计算左子树的值
	if(now == 1 && a[v].c == '|'){ans2++;return 1;} 
	if(now == 0 && a[v].c == '&'){ans1++;return 0;} //判断短路的两种情况 ， 返回对应计算值
	return dfs(a[v].r);//未发生短路则子树的值就是右子树的值
}
1
2
3
4
5
6
7
8

#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N = 1e6 + 10;

string s;
stack<char>st;
vector<char>ve;
struct node{
	char c;
	int l,r;
}a[N];
int cnt , ans1 , ans2;

void change(){
	int len = s.size();
	for(int i=0;i<len;i++){
		if(isdigit(s[i])) ve.push_back(s[i]);
		else if(st.empty() || s[i] == '(')  st.push(s[i]);
		else if(s[i] == ')'){
			while(st.top() != '(') ve.push_back(st.top()) , st.pop();
			st.pop();//左括号出栈
		}else if(s[i] == '&'){
			while(!st.empty() && st.top() == '&')  ve.push_back(st.top()) , st.pop(); st.push(s[i]);
		}else{
			while(!st.empty() && st.top() == '&' || !st.empty() && st.top() == '|')  ve.push_back(st.top()) , st.pop(); st.push(s[i]);
		}	
	}
	
	while(!st.empty()) ve.push_back(st.top()) , st.pop();
}

void build(){
	stack<int>sts;
	for(auto k : ve){
		if(k == '0' || k == '1') a[++cnt] = {k,-1,-1} , sts.push(cnt) ;
		else{
			int r = sts.top();sts.pop() , l = sts.top();sts.pop();
			a[++cnt] = {k,l,r};sts.push(cnt);
		}
	}
}

int dfs(int v){
	
	if(a[v].c == '1' || a[v].c == '0') return a[v].c - '0';
	int now = dfs(a[v].l);
	if(now == 1 && a[v].c == '|'){ans2++;return 1;}
	if(now == 0 && a[v].c == '&'){ans1++;return 0;}
	return dfs(a[v].r);
}


int main(){
	
	cin >> s;
	change();
	build();
	cout << dfs(cnt) << "\n" ; 
	cout << ans1 << " " << ans2;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62