♐ CSP_J 组真题
2022年
3. 逻辑表达式

线上OJ:

https://www.jisuanke.com/problem/T3732 (opens in a new tab)
https://www.luogu.com.cn/problem/P8815 (opens in a new tab)

核心思想:

遇题不慌,先分析

  1. 遇到 0& 时(本身 ans1++):
    1.1 如果后面紧跟着 &,则 ans1++。 举例,因为 0&*&*& 的结果取决于第一个 0&,后面的两个 & 符号都可以跳过,所以在 0& 后面每遇到一个连续的 & 就执行一次 ans1++
    1.2 如果后面是左括号 ( 则一直找到对应的右括号 ),括号中间的都不用计算,也不用统计跳过次数。如果最外面的括号 () 中间还有多组括号,都跳过
    1.3 如果后面跟的是 |,则 直接记录 | 右边的数值。因为 0& 一定是 0 ,所以对于 0&*|* 这个表达式的结果其实取决于 | 的右半边。
  2. 遇到 1| 时(本身 ans2++):
    2.1 如果后面紧跟着 |,则 ans2++。 举例,因为 1|*|*| 的结果取决于第一个 1|,后面的两个 | 符号都可以跳过,所以在 1| 后面每遇到 一个连续的 | 就执行一次 ans2++
    2.2 如果后面是左括号 ( 则一直找到对应的右括号 ),括号中间的都不用计算,也不用统计跳过次数。如果最外面的括号 () 中间还有多组括号,都跳过
    2.3 如果后面跟的是 &(此时较特殊:因为 & 的优先级高于 |,所以此时的 1|*&* 可以理解为 1|(*&*)
    此时就变成了 2.2 的状态。括号内的都不用计算,也不用统计跳过次数。因为都被 1| 给跳过了。 所以此时 1| 的效果依然继续向后传递。也就是在 2.3时什么都不用处理

题解代码:

#include<bits/stdc++.h>
using namespace std;
 
string str;
bool val;		// 表达式的值 
int ans1, ans2;	// ans1记录 0& 跳过的次数,ans2记录 1| 跳过的次数, 
int status; 		//status 判断是否要跳掉,1 为 0&,2 为 1|,0 不用跳 
 
int main()
{
//	cerr<<(&st-&ed)/1024.0/1024.0;
	cin >> str;
	for(int i=0;i<str.size();i++)
	{
		if(status)
		{
			if(str[i] == '(')
			{	// 1.2 和 2.2 , 括号内的都可以跳过 
				int x = 1;
				while(x)
				{
					i++;
					if(str[i] == '(') 	x++;
					if(str[i] == ')') 	x--;
				}
			}
			else if( status==1 && str[i]=='|' )	status = 0;	// 1.3			
			else if( status==1 && str[i]=='&' )	ans1++;		// 1.1
			else if( status==2 && str[i]=='|' )	ans2++;		// 2.1 
			else if( status==2 && str[i]=='&' ){	}		// 2.3
			else if( str[i] == ')' )			status = 0;					
		}
		else
		{
			if(str[i] == '1') 	val=1;
			if(str[i] == '0') 	val=0;
			if(str[i] == '&' && val==0){
				status=1;
				ans1++;
			}
			if(str[i] == '|' && val==1){
				status=2;
				ans2++;
			} 
		}
	}
	cout << val << endl;
	cout << ans1 << " " << ans2 << endl;
 
	return 0;
}