原题链接:https://www.luogu.com.cn/problem/P8815
题意解读:计算逻辑表达式的值以及&,|短路操作的次数。
解题思路:
又是一道经典的中缀表达式的变形问题,
如果对中缀表示式如何求值不理解,移步https://www.acwing.com/problem/content/3305/进行复习
如果对表示式如何构建树形结构以及通过树形结构来求值不理解,可以移步https://www.cnblogs.com/jcwy/p/18247992进行复习
对于本题:思路是通过双栈来将中缀表达式构建成树形结构
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
string expr;
stack<int> op; //运算符栈,存的都是树的节点编号
stack<int> num; //操作数栈,存的都是树的节点编号
int l[N], r[N], w[N], idx; //二叉树每个节点的的左子树、右子树、值,idx是节点编号
char o[N]; //二叉树每个符号节点的内容: &,|
int ans1, ans2;
map<char, int> priority = {{'|', 1}, {'&', 2}}; //定义|和&的优先级
void eval()
{
int a = num.top(); num.pop();
int b = num.top(); num.pop();
int x = op.top(); op.pop();
int res;
if(o[x] == '&') res = w[a] & w[b];
if(o[x] == '|') res = w[a] | w[b];
//构建树,先入栈的b为x左子节点,后入栈的a为x右子节点
l[x] = b, r[x] = a;
//更新x节点的值
w[x] = res;
//计算之后的结果节点编号入num栈
num.push(x);
}
void dfs(int root)
{
if(o[root] == '&')
{
if(w[l[root]] == 0) ans1++, dfs(l[root]); //左子结点是0,a&b短路次数+1
else dfs(l[root]), dfs(r[root]);
}
else if(o[root] == '|')
{
if(w[l[root]] == 1) ans2++, dfs(l[root]); //左子结点是1,a|b短路次数+1
else dfs(l[root]), dfs(r[root]);
}
}
int main()
{
cin >> expr;
for(int i = 0; i < expr.size(); i++)
{
if(expr[i] == '0' || expr[i] == '1')
{
w[++idx] = expr[i] - '0'; //生成操作数在树中节点编号,节点值保存
num.push(idx); //数字节点入num栈
}
else if(expr[i] == '(')
{
o[++idx] = expr[i]; //生成节点编号,节点值保存
op.push(idx); //左括号节点直接入op栈
}
else if(expr[i] == ')') //右括号,要从栈中取出操作数和运算符构建树
{
while(o[op.top()] != '(') eval();
op.pop(); //弹出'('
}
else if(expr[i] == '&' || expr[i] == '|')
{
while(op.size() && priority[expr[i]] <= priority[o[op.top()]]) //如果当前符号优先级<=当前栈顶符号优先级
eval();
o[++idx] = expr[i]; //生成运算符在树中节点编号,节点值保存
op.push(idx); //将符号节点入op栈
}
}
while(op.size()) eval();
cout << w[num.top()] << endl;
dfs(num.top());
cout << ans1 << " " << ans2;
return 0;
}
标签:P8815,int,expr,节点,num,2022,root,CSP,op From: https://www.cnblogs.com/jcwy/p/18257526