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

【测试用例翔实栈】P8815 [CSP-J 2022] 逻辑表达式

article 2025/2/7 17:18:53

本文涉及知识点

C++栈

[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

【样例 #3】

见附件中的 expr/expr3.in 与 expr/expr3.ans。

【样例 #4】

见附件中的 expr/expr4.in 与 expr/expr4.ans。

【数据范围】

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据， $\le \lvert s \rvert \le {10}^6$ 。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$
中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表
达式）。

测试点编号	$\lvert s \rvert \le$	特殊条件
$\sim 2$	$3$	无
$\sim 4$	$5$	无
$5$	$2000$	1
$6$	$2000$	2
$7$	$2000$	3
$\sim 10$	$2000$	无
$\sim 12$	${10}^6$	1
$\sim 14$	${10}^6$	2
$\sim 17$	${10}^6$	3
$\sim 20$	${10}^6$	无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

字符串 0 和 1 是符合规范的；
如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
所有符合规范的逻辑表达式均可由以上方法生成。

栈运算

经典的运算：
如果当前是运算数：如果栈顶是高级运算符(&)，则马上运算；否则加入到运算数栈。
如果是与或左括号，入运算符栈。
如果遇到右括号或结束，不断进行运算直到运算符栈为空；或遇到左括号，左括号出栈后，结束。
运算数包括结果和短路次数。
&：运算数1是0，&短路次数是运算数1的短路次数+1，|短路次数和运算数1同；否则：两个运算数短路次数之和。
|：运算数1是1，|短路次数是运算数1的短路次数+1，&短路次数和运算数1同；否则：两个运算数短路次数之和。
注意：
如果只运算结果，|从左到右和从右向左完全一样。计算短路次数这样算，就不行。可以：
出栈到临时栈，在临时栈中计算。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	scanf("%d", &n);
	vector<T> ret(n);
	for(int i=0;i < n ;i++) {
		cin >> ret[i];
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

class Solution {
public:
	tuple<int, int, int> Ans(string& s) {
		for (const auto& ch : s) {
			if (')' == ch) {
				Do();
			}
			else if (('0' <= ch) && (ch <= '1')) {
				m_num.emplace(ch - '0', 0, 0);
				DoAnd();
			}
			else {
				m_ope.emplace(ch);
			}
		}
		Do();
		return m_num.top();
	}
	void Do() {//处理右括号
		if (m_ope.empty()) { return; }
		stack<char> ope;
		stack<tuple<int, int, int>> num;
		num.emplace(m_num.top());
		m_num.pop();
		while (m_ope.size() && ('(' != m_ope.top())) {
			num.emplace(m_num.top());
			m_num.pop();
			ope.emplace(m_ope.top());
			m_ope.pop();
		}
		if (m_ope.size()) { m_ope.pop(); }
		while (DoOr(ope, num));
		m_num.emplace(num.top());
		DoAnd();
	}
	static bool DoOr(stack<char>& ope, stack<tuple<int, int, int>>& num) {
		if (ope.empty()) { return false; }
		const auto [v1, c1, cc1] = num.top();
		num.pop();
		const auto [v2, c2, cc2] = num.top();
		num.pop();
		ope.pop();
		auto v3 = v1 | v2;
		auto c3 = (1 == v1) ? (c1) : (c1 + c2);
		auto cc3 = (1 == v1) ? (cc1 + 1) : (cc1 + cc2);
		num.emplace(v3, c3, cc3);
		return true;
	}
	bool DoAnd() {
		if (m_ope.empty() || ('&' != m_ope.top())) { return false; }
		const auto [v2, c2, cc2] = m_num.top();
		m_num.pop();
		const auto [v1, c1, cc1] = m_num.top();
		m_num.pop();
		m_ope.pop();
		auto v3 = v1 & v2;
		auto c3 = (0 == v1) ? (c1 + 1) : (c1 + c2);
		auto cc3 = (0 == v1) ? (cc1) : (cc1 + cc2);
		m_num.emplace(v3, c3, cc3);
		return true;
	}
	stack<char> m_ope;
	stack<tuple<int, int, int>> m_num;
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	string s;
	cin >> s;
	auto res = Solution().Ans(s);
#ifdef _DEBUG		
	//printf("K=%d", K);
	//Out(b, "b=");
	//Out(c, "c=");
#endif // DEBUG	
	cout << get<0>(res) << endl << get<1>(res) << " " << get<2>(res);
	return 0;
}

单元测试

	string s;
		TEST_METHOD(TestMethod1)
		{
			s = "0";
			auto res = Solution().Ans(s);
			AssertEx({ 0,0,0 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "(0)";
			auto res = Solution().Ans(s);
			AssertEx({ 0,0,0 }, res);
		}
		TEST_METHOD(TestMethod3)
		{
			s = "((0))";
			auto res = Solution().Ans(s);
			AssertEx({ 0,0,0 }, res);
		}
		TEST_METHOD(TestMethod4)
		{
			s = "((0&0))";
			auto res = Solution().Ans(s);
			AssertEx({ 0,1,0 }, res);
		}
		TEST_METHOD(TestMethod5)
		{
			s = "((0&1))";
			auto res = Solution().Ans(s);
			AssertEx({ 0,1,0 }, res);
		}
		TEST_METHOD(TestMethod6)
		{
			s = "((1&0))";
			auto res = Solution().Ans(s);
			AssertEx({ 0,0,0 }, res);
		}
		TEST_METHOD(TestMethod7)
		{
			s = "((1&1))";
			auto res = Solution().Ans(s);
			AssertEx({ 1,0,0 }, res);
		}

		TEST_METHOD(TestMethod14)
		{
			s = "((0|0))";
			auto res = Solution().Ans(s);
			AssertEx({ 0,0,0 }, res);
		}
		TEST_METHOD(TestMethod15)
		{
			s = "((0|1))";
			auto res = Solution().Ans(s);
			AssertEx({ 1,0,0 }, res);
		}
		TEST_METHOD(TestMethod16)
		{
			s = "((1|0))";
			auto res = Solution().Ans(s);
			AssertEx({ 1,0,1 }, res);
		}
		TEST_METHOD(TestMethod17)
		{
			s = "((1|1))";
			auto res = Solution().Ans(s);
			AssertEx({ 1,0,1 }, res);
		}
		TEST_METHOD(TestMethod31)
		{
			s = "0&(1|0)|(1|1|1&0)";
			auto res = Solution().Ans(s);
			AssertEx({ 1,1,2 }, res);
		}
		TEST_METHOD(TestMethod32)
		{
			s = "(0|1&0|1|1|(1|1))";
			auto res = Solution().Ans(s);
			AssertEx({ 1,0,2 }, res);
		}
		TEST_METHOD(TestMethod33)
		{
			s = "(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0";
			auto res = Solution().Ans(s);
			AssertEx({ 0,2,3 }, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功