[CSP-J 2022] 逻辑表达式

题目来源：洛谷题库

[CSP-J 2022] 逻辑表达式

题目描述

逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

在一个逻辑表达式中，元素的值只有两种可能：$0$（表示假）和 $1$（表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 &）和“或”（符号为 |）。其运算规则如下：

$0\&0=0\&1=1\&0=0$，$1\&1=1$；
$0|0=0$，$0|1=1|0=1|1=1$。

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算；两种运算并列时，& 运算优先于 | 运算；同种运算并列时，从左向右运算。

比如，表达式 0|1&0 的运算顺序等同于 0|(1&0)；表达式 0&1&0|1 的运算顺序等同于 ((0&1)&0)|1。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 a&b 的逻辑表达式中，会先计算 a 部分的值，如果 $a=0$，那么整个逻辑表达式的值就一定为 $0$，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 a 部分的值，如果 $a=1$，那么整个逻辑表达式的值就一定为 $1$，无需再计算 b 部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处“短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处“短路”。

输入格式

输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

输出格式

输出共两行，第一行输出一个字符 0 或 1，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和 a|b 的“短路”各出现了多少次。

样例 #1

样例输入 #1

0&(1|0)|(1|1|1&0)

样例输出 #1

1
1 2

样例 #2

样例输入 #2

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

样例输出 #2

0
2 3

提示

【样例解释 #1】

该逻辑表达式的计算过程如下，每一行的注释表示上一行计算的过程：

0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1

题意：

• 计算出表达式的值，计算时候优先级（）> & > |
• 分别记录短路：0& 和1| 的短路次数

思路：

• 判度短路很简单，从前往后遍历时，遇到0& 和1|记录出现次数即可

• 计算表达式：考虑栈来储存，然后遇到）或者符号+数字可以先出栈计算再入栈，但是要考虑优先级的问题，因为&>| ，，所以栈来储存反而记录优先级比较麻烦。 所以考虑下是否有特殊性质可以直接去处理
  $0\&0=0\&1=1\&0=0$，$1\&1=1$；
  $0|0=0$，$0|1=1|0=1|1=1$。

• 仔细观察不难发现 ：如果是短路，①与运算短路’1|‘，后面不论数据多长，遇到“）”之前都可以直接跳过不计算，遇到“|”则继续+1即可。②与运算短路’0&’，如果遇到“|”、“）”则会结束短路，遇到&则跳过不计算，短路值+1即可 （遇到子级（）则直接跳过，也不记录短路情况）

• 如果不短路（1&或者0|）：
  ，，，&0=0；，，，&1=1，，，，|0=0；，，，|1=1， 所以其值就等于最后一个符号后面的数值，而且也不必在意优先级，后面决定最终的值，要么就是前面的&不重要，要么就是后面的&已经作为计算结果了

• 因此，根据以上性质，直接暴力模拟这个过程即可

数据约束：

字符串在10^6范围内，所以不会存在超时

参考代码：

//记录是否是短路的情况，0&/  1|
//正常计算 
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
int f=1,c=0,ans=0; //f=1表示正常运算，=0表示短路运算。c=0为与运算c=1为或运算
int s0=0,s1=0;//分别表示或运算、与运算的短路次数 
cin>>s;
int len = s.size();
for(int i=0;i<len;i++){
if(f){
if(s[i]=='&'&&ans==0) f=0,c=0,s0++; //与短路 
else if(s[i]=='|'&&ans==1) f=0,c=1,s1++;//或短路 
else {
//正常计算，取决于符号后面的值 
if(s[i]=='1') ans= 1;
else if(s[i]=='0') ans = 0;
else continue;//是符号就继续往后面遍历即可 
}
}
else{
if(s[i]==')') f=1; //运算遇到）正常计算
else if(c==1 &&s[i]=='|') s1++; 
else if(c==0 &&s[i]=='&') s0++; 
else if(c==0 &&s[i]=='|') f=1; //0& 遇到或运算结束 
else if(s[i]=='('|s[i]==')'){//遇到（）的情况 ，子级括号都直接跳过 ,不计算 
int num = 0;//括号对数 
//遇到子级括号的情况 
if(s[i]=='(') num++;
while(num){
i++;
if(s[i]=='(') num++;
else if(s[i]==')') num--;
} 
} 
} 
} 
cout<<ans<<endl;
cout<<s0<<" "<<s1;

   return 0;
}

原文地址：https://blog.csdn.net/m0_46183615/article/details/142704604

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！