信息学奥赛一本通 2088：【22CSPJ普及组】逻辑表达式(expr) | 洛谷 P8815 [CSP-J 2022] 逻辑表达式

【题目链接】

ybt 2088：【22CSPJ普及组】逻辑表达式(expr)
洛谷 P8815 [CSP-J 2022] 逻辑表达式

【题目考点】

1. 表达式树：中缀表达式建树

可以看该问题信息学奥赛一本通 1356：计算(calc)
了解中缀表达式建树过程。

【解题思路】

解法1：中缀表达式建树

中缀表达式建立表达式树的过程：

1. 设结点栈nStk保存结点地址、运算符栈cStk保存运算符。
   设函数pri返回运算符优先级，其中'('优先级最高，')'优先级最低，'&'优先级比'|'高。
   设函数calc完成一步基本的'&'运算以及'|'运算。
   从左向右扫描表达式字符串：
2. 遇到数字时，构建数字结点，将结点地址加入结点栈。
3. 遇到运算符时，入栈条件为：栈空，或该运算符优先级比栈顶运算符优先级高，或者栈顶是'('。只有不满足该条件，则一直出栈。
   运算符出栈后，从结点池申请新结点作为这棵子树的根结点，新结点地址为np。结点np的运算符属性node[np].c设为出栈的运算符cStk.top()。
   结点栈先出栈右孩子地址rp、再出栈左孩子地址lp，两个结点作为结点np的左右孩子，使用左右孩子的值node[lp].n和node[rp].n结合结点np的运算符node[np].c进行运算，将运算结果结果设为结点np的值node[np].n，将该结点的地址np入栈结点栈。
   如果要入栈的是')'且栈顶是'('，那么二者配对，出栈运算符。否则运算符入栈。
4. 可以预先在字符串末尾加上一个优先级最低的')'，以促使运算符栈中的运算符都出栈。
5. 最后结点栈的栈顶即为整个中缀表达式建树得到的树的根结点地址，该结点的值即为整个表达式的值。

输出整个表达式的值后，需要统计&运算短路以及|运算短路发生的次数。
&运算第一个运算数的值为0时会发生&运算短路，
|运算第一个运算数的值为1时会发生|运算短路。
ansAnd计数&运算短路次数，ansOr计数|运算短路次数。
表达式树中，结点的值就是以该结点为根的表达式树对应的表达式的值。
从根结点开始深度优先搜索整棵表达式树。

• 如果当前结点的运算符为’&'，且左孩子的值为0，则发生&运算短路，ansAnd计数增加1。接下来只需要搜索左子树，不需要搜索右子树，因为右子树表示的表达式不进行运算。
• 如果当前结点的运算符为’|'，且左孩子的值为1，则发生|运算短路，ansOr计数增加1。接下来只需要搜索左子树，不需要搜索右子树，因为右子树表示的表达式不进行运算。
• 对于其它情况，分别搜索左右子树。

最后输出两种运算短路发生的次数ansAnd和ansOr。

解法2：找规律

从前向后遍历表达式字符串
设sta表示当前的状态，设val表示当前已遍历过的表达式求出的数值。
当前状态有3种：

• 状态1：如果val为0，当前处在在0&后的位置。如果val为1，当前处在1|后的位置
• 状态0：其他情况，包括起始位置，以及1&，0|后的情况。

开始时状态sta的值为0，val的值为0。

• 如果当前位置是数字：
  • 如果当前是状态0，那么直接把val设为当前数字的值。（如果起始是x，当前值为x。如果是1&x，0|x，当前的值也为x）
  • 如果当前是状态1，此处的数字对数值没有影响。(因为0&x的值都为0，1|x的值都为1）
• 如果当前位置是&
  • 如果val为0，是状态0或状态1，此时处于0&情况，&短路次数增加1，进入状态1。
  • 如果val为1：
    • 如果此时是状态1，说明此时处于1|x&y的情况，正在访问后面的&运算符。由于&的优先级比|高，所以这一段表达式遍历后，val的值应该为1，而且处于状态1。也就是说此时应该不做操作。
    • 如果此时是状态0且val为1，此时是1&的情况，运算后仍然是状态0，不需要做操作。
    • 因此val为1时不需要操作。
• 如果当前位置是|
  • 如果val为1，是状态0或状态1，此时处于1|的情况，|短路次数增加1，进入状态1。
  • 如果val为0：
    • 如果处于状态1，此时处于0|的情况，运算后变为状态0。
    • 如果处于状态0，不需要操作，也可以将状态设为0。
    • 因此val为0时可以将状态设为0。
• 如果当前位置是(
  • 如果当前处于状态1，此时处于1|(...)或0&(...)的情况，从当前左括号到与其对应的右括号，这对括号内表达式的值是不起作用的，已知运算到右括号结束，此时仍处于状态1，val不变。
  • 如果当前处于状态0，就当做没有这个左括号或右括号，直接计算括号内的值，改变val的值。
• 如果当前位置是)
  访问与其配对的左括号时一定是状态0，左右括号都需要直接略过。括号结束后，在括号内的表达式的状态不会影响括号外的情况，应该变回状态0。

最后输出val的值，以及&短路和|短路的次数。

【题解代码】

解法1：中缀表达式建树

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
struct Node
{
	int n;
	char c;
	int left, right;
} node[N];
int p, ansAnd, ansOr;//ansAnd：0&短路的次数 ansOr：1|短路的次数 
int pri(char c)
{
	switch(c)
	{
		case '(': return 4;
		case '&': return 3;
		case '|': return 2;
		case ')': return 1;
	}
}
int calc(int a, int b, char c)
{
	switch(c)
	{
		case '&': return a && b;
		case '|': return a || b;
	}
}
void dfs(int r)
{
	if(node[r].c == '\0')//r是数值结点（叶子结点） 
		return;
	int lval = node[node[r].left].n;//r->left->n左孩子的值，即运算符node[r].c左侧表达式的值。
	dfs(node[r].left);
	if(lval == 0 && node[r].c == '&')
		ansAnd++;
	else if(lval == 1 && node[r].c == '|')
		ansOr++;
	else
		dfs(node[r].right);
}
int main()
{
	string s;
	stack<int> nStk;
	stack<char> cStk;
	cin >> s;
	s += ')';//促使最后运算符栈剩余运算符出栈
	for(char c : s)
	{
		if(c == '0' || c == '1')
		{
			int np = ++p;
			node[np].n = c-'0';
			nStk.push(np);
		}
		else
		{
			while(!(cStk.empty() || pri(c) > pri(cStk.top()) || cStk.top() == '('))
			{
				int np = ++p;
				node[np].c = cStk.top();
				int rp = nStk.top();
				nStk.pop();
				int lp = nStk.top();
				nStk.pop();
				node[np].left = lp, node[np].right = rp;
				node[np].n = calc(node[lp].n, node[rp].n, node[np].c);
				nStk.push(np);
				cStk.pop();
			}
			if(c == ')')
				cStk.pop();
			else
				cStk.push(c);
		}
	}
	int root = nStk.top();
	cout << node[root].n << endl;
	dfs(root);
	cout << ansAnd << ' ' << ansOr;
	return 0;
}

解法2：找规律

#include<bits/stdc++.h>
using namespace std;
string s;
int sta, val, ansAnd, ansOr;  
int findBracket(string &s, int i)//此处必须传引用，否则复制字符串s会导致时间超限 
{//s[i]是左括号，找到与s[i]配对的右括号的位置（保证有该右括号） 
	int b = 1;//未配对的左括号的数量 
	for(int j = i+1; j < s.length(); ++j) 
	{
		if(s[j] == '(')
			b++;
		else if(s[j] == ')')
			if(--b == 0)
				return j; 
	}
	return s.length();//保持函数各路径都有返回值，不会运行到这一句 
}
int main()
{
	cin >> s;
	for(int i = 0; i < s.length(); ++i)
	{
		if(s[i] >= '0' && s[i] <= '9')
		{	
			if(sta == 0)
				val = s[i]-'0';
		}
		else if(s[i] == '&')
		{
			if(val == 0)
			{
				ansAnd++;
				sta = 1;
			} 
		}
		else if(s[i] == '|')
		{
			if(val == 1)
			{
				ansOr++;
				sta = 1;
			}
			else
				sta = 0;
		} 
		else if(s[i] == '(') 
		{
			if(sta == 1)//略过这对括号中的表达式
				i = findBracket(s, i);
		}
		else if(s[i] == ')')
			sta = 0; 
	}
	cout << val << endl << ansAnd << ' ' << ansOr;
	return 0;
}