P8815 [CSP-J 2022] 逻辑表达式

Problem

考察算法：后缀表达式计算、建表达式树、\(DFS\)。

题目简述

给你一个中缀表达式，其中只有 \(\&\) 和 \(\mid\) 两种运算。

求：\(\&\) 和 \(\mid\) 运算中的“最短路”次数各出现了多少次。

最短路的定义为：

• 在 \(a\) \(\&\) \(b\) 运算中，如果 \(a = 0\)，那么整个表达式的计算就不需要再继续进行了，因为表达式的值都一定为 \(0\)。

• 在 \(a\) \(\mid\) \(b\) 运算中，如果 \(a = 1\)，表达式的值也不需要再继续计算了，一定为 \(1\)。

以上两种情况中的任何一种，都被称作一次“最短路”的情况。

思路

• 首先把中缀表达式转换为后缀表达式。
• 在计算后缀表达式的过程中，建立一颗表达式树。
• 最后 \(dfs\) 整棵树，看看最短路各出现了多少次。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
struct node{
	char c;
	int l, r, v;
} a[N];
stack<char> op;
stack<int> st;
vector<char> v;
char s[N];
int c1, c2;

void dfs(int x) {
	if (a[x].l == 0 && a[x].r == 0) return;
	int t1 = a[x].l, t2 = a[x].r;
	dfs(t1);
	if (a[x].c == '&' && a[t1].v == 0) { c1++; return; }
	if (a[x].c == '|' && a[t1].v == 1)  { c2++; return; }
	dfs(t2);
}

int main() {
	scanf("%s", s + 1);
	for (int i = 1, len = strlen(s + 1); i <= len; i++) {
		if (isdigit(s[i])) v.push_back(s[i]);
		else if (s[i] == '(') op.push(s[i]);
		else if (s[i] == ')') {
			while (!op.empty() && op.top() != '(') {
				v.push_back(op.top());
				op.pop();
			}
			op.pop();
		} else if (s[i] == '&') {
			while (!op.empty() && op.top() == '&') {
				v.push_back(op.top());
				op.pop();
			}
			op.push(s[i]);
		} else if (s[i] == '|') {
			while (!op.empty() && (op.top() == '&' || op.top() == '|')) {
				v.push_back(op.top());
				op.pop();
			}
			op.push(s[i]);
		}
	}
	while (!op.empty()) {
		v.push_back(op.top());
		op.pop();
	}
	int len = v.size(), k = 0;
	for (int i = 0; i < len; i++) {
		if (isdigit(v[i])) {
			a[++k] = {0, 0, 0, v[i] - '0'};
			st.push(k);
		} else {
			int x = st.top(); st.pop();
			int y = st.top(); st.pop();
			if (v[i] == '&') {
				a[++k] = {v[i], y, x, a[y].v & a[x].v};
				st.push(k);
			} else {
				a[++k] = {v[i], y, x, a[y].v | a[x].v};
				st.push(k);
			}
			
		}
	}
	printf("%d\n", a[k].v);
	dfs(k);
	printf("%d %d", c1, c2);
	return 0;
}