【栈】1106. 剖析布尔表达式

本文涉及知识点

栈
LeetCode 1106. 剖析布尔表达式

布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：
‘t’，运算结果为 true
‘f’，运算结果为 false
‘!(subExpr)’，运算过程为对内部表达式 subExpr 举行 逻辑非（NOT）运算
‘&(subExpr1, subExpr2, …, subExprn)’，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, …, subExprn 举行 逻辑与（AND）运算
‘|(subExpr1, subExpr2, …, subExprn)’，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, …, subExprn 举行 逻辑或（OR）运算
给你一个以字符串情势表述的 布尔表达式 expression，返回该式的运算结果。
标题测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。
示例 1：
输入：expression = “&(|(f))”
输出：false
解释：
首先，计算 |(f) --> f ，表达式变为 “&(f)” 。
接着，计算 &(f) --> f ，表达式变为 “f” 。
最后，返回 false 。
示例 2：
输入：expression = “|(f,f,f,t)”
输出：true
解释：计算 (false OR false OR false OR true) ，结果为 true 。
示例 3：
输入：expression = “!(&(f,t))”
输出：true
解释：
首先，计算 &(f,t) --> (false AND true) --> false --> f ，表达式变为 “!(f)” 。
接着，计算 !(f) --> NOT false --> true ，返回 true 。
提示：
1 <= expression.length <= 2 * 104
expression 为 ‘(’、‘)’、‘&’、‘|’、‘!’、‘t’、‘f’ 和 ‘,’ 之一
递归

这个容易想到。
栈

不需要数据栈，只需要操纵符栈。本题运算符和操纵数都是单字符，很好剖析。
除逗号和右括号外，全部入栈。
忽略逗号。
碰到右括号，出栈直到左括号出栈。
记录出栈的 t f数量。记录并出栈运算符。
运算结果入栈。
代码

1. class Solution {
2. public:
3.         bool parseBoolExpr(string exp) {
4.                 for (const auto& ch : exp) {
5.                         if (',' == ch) { continue; }
6.                         if (')' == ch) {
7.                                 int cnts[2] = { 0 };
8.                                 while ('(' != m_sta.top()) {
9.                                         cnts['t' == m_sta.top()]++;
10.                                         m_sta.pop();
11.                                 }
12.                                 m_sta.pop();
13.                                 bool bRet = true;
14.                                 if ('&' == m_sta.top()) {
15.                                         bRet = (0 == cnts[0]);
16.                                 }else if ('|' == m_sta.top()) {
17.                                         bRet = (0 != cnts[1]);
18.                                 }
19.                                 else {
20.                                         bRet = cnts[0];
21.                                 }
22.                                 m_sta.pop();
23.                                 m_sta.push(bRet ? 't' : 'f');
24.                                 continue;
25.                         }
26.                         m_sta.emplace(ch);
27.                 }
28.                 return 't' == m_sta.top();
29.         }
30.         stack<char> m_sta;
31. };

复制代码

单元测试

1. template<class T1,class T2>
2. void AssertEx(const T1& t1, const T2& t2)
3. {
4.         Assert::AreEqual(t1 , t2);
5. }
7. template<class T>
8. void AssertEx(const vector<T>& v1, const vector<T>& v2)
9. {
10.         Assert::AreEqual(v1.size(), v2.size());       
11.         for (int i = 0; i < v1.size(); i++)
12.         {
13.                 Assert::AreEqual(v1[i], v2[i]);
14.         }
15. }
17. template<class T>
18. void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
19. {
20.         sort(vv1.begin(), vv1.end());
21.         sort(vv2.begin(), vv2.end());
22.         Assert::AreEqual(vv1.size(), vv2.size());
23.         for (int i = 0; i < vv1.size(); i++)
24.         {
25.                 AssertEx(vv1[i], vv2[i]);
26.         }
27. }
29. namespace UnitTest
30. {
31.         string expression;
32.         TEST_CLASS(UnitTest)
33.         {
34.         public:
35.                 TEST_METHOD(TestMethod0)
36.                 {
37.                         expression = "&(|(f))";
38.                         auto res = Solution().parseBoolExpr(expression);
39.                         AssertEx(false,res);
40.                 }
41.                 TEST_METHOD(TestMethod1)
42.                 {
43.                         expression = "|(f,f,f,t)";
44.                         auto res = Solution().parseBoolExpr(expression);
45.                         AssertEx(true, res);
46.                 }
47.                 TEST_METHOD(TestMethod2)
48.                 {
49.                         expression = "!(&(f,t))";
50.                         auto res = Solution().parseBoolExpr(expression);
51.                         AssertEx(true, res);
52.                 }
53.         };
54. }

复制代码

扩展阅读

视频课程

有效学习：明确的目的 及时的反馈 拉伸区（难度符合），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
怎样你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相干下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对各人说的话《喜缺全书算法册》以原理、正确性证明、总结为主。闻缺陷则喜是一个精美的愿望，早发现问题，早修改问题，给老板节省钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。假如步伐是一条龙，那算法就是他的是睛 测试环境

操纵系统：win7 开发环境： VS2019 C++17
大概 操纵系统：win10 开发环境： VS2022 C++17
如无特殊阐明，本算法用**C++**实现。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。