当前位置：首页 > article >正文

[CSP-J 2022] 逻辑表达式

article 2024/10/4 18:55:22

题目来源：洛谷题库

[CSP-J 2022] 逻辑表达式

题目描述

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

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

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