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;
}