本文涉及知识点
C++栈
[CSP-J 2022] 逻辑表达式
题目描述
逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。
在一个逻辑表达式中，元素的值只有两种可能： 0 0 0（表示假）和 1 1 1（表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 &）和“或”（符号为 |）。其运算规则如下：
0 & 0 = 0 & 1 = 1 & 0 = 0 0 \mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0 0&0=0&1=1&0=0， 1 & 1 = 1 1 \mathbin{\&} 1 = 1 1&1=1；
0 ∣ 0 = 0 0 \mathbin{|} 0 = 0 0∣0=0， 0 ∣ 1 = 1 ∣ 0 = 1 ∣ 1 = 1 0 \mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1 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 a = 0 a=0，那么整个逻辑表达式的值就一定为 0 0 0，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 a 部分的值，如果 a = 1 a = 1 a=1，那么整个逻辑表达式的值就一定为 1 1 1，无需再计算 b 部分的值。
现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处“短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处“短路”。
输入格式
输入共一行，一个非空字符串 s s 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。
【数据范围】
设 ∣ s ∣ \lvert s \rvert ∣s∣ 为字符串 s s s 的长度。
对于所有数据， 1 ≤ ∣ s ∣ ≤ 10 6 1 \le \lvert s \rvert \le {10}^6 1≤∣s∣≤106。保证 s s s 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 s s s
中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表
达式）。
| 测试点编号 | ∣ s ∣ ≤ \lvert s \rvert \le ∣s∣≤ | 特殊条件 |
|---|---|---|
| 1 ∼ 2 1 \sim 2 1∼2 | 3 3 3 | 无 |
| 3 ∼ 4 3 \sim 4 3∼4 | 5 5 5 | 无 |
| 5 5 5 | 2000 2000 2000 | 1 |
| 6 6 6 | 2000 2000 2000 | 2 |
| 7 7 7 | 2000 2000 2000 | 3 |
| 8 ∼ 10 8 \sim 10 8∼10 | 2000 2000 2000 | 无 |
| 11 ∼ 12 11 \sim 12 11∼12 | 10 6 {10}^6 106 | 1 |
| 13 ∼ 14 13 \sim 14 13∼14 | 10 6 {10}^6 106 | 2 |
| 15 ∼ 17 15 \sim 17 15∼17 | 10 6 {10}^6 106 | 3 |
| 18 ∼ 20 18 \sim 20 18∼20 | 10 6 {10}^6 106 | 无 |
其中：
特殊性质 1 为：保证 s s s 中没有字符 &。
特殊性质 2 为：保证 s s s 中没有字符 |。
特殊性质 3 为：保证 s s 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 _DEBUGfreopen("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);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
