网站建设 做一个网站需要多少钱,凡客v十商城,苏州网站建设设计制作公司怎么样,建设文化网站的目的和意义本文涉及知识点
栈
LeetCode 1106. 解析布尔表达式
布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定#xff1a; ‘t’#xff0c;运算结果为 true ‘f’#xff0c;运算结果为 false ‘!(subExpr)’#xff0c;运算过程为对内部表达式…本文涉及知识点
栈
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[i] 为 ‘(’、‘)’、‘’、‘|’、‘!’、‘t’、‘f’ 和 ‘,’ 之一
递归
这个容易想到。
栈
不需要数据栈只需要操作符栈。本题运算符和操作数都是单字符很好解析。 除逗号和右括号外全部入栈。 忽略逗号。 遇到右括号出栈直到左括号出栈。 记录出栈的 t f数量。记录并出栈运算符。 运算结果入栈。
代码
class Solution {
public:bool parseBoolExpr(string exp) {for (const auto ch : exp) {if (, ch) { continue; }if () ch) {int cnts[2] { 0 };while (( ! m_sta.top()) {cnts[t m_sta.top()];m_sta.pop();}m_sta.pop();bool bRet true;if ( m_sta.top()) {bRet (0 cnts[0]);}else if (| m_sta.top()) {bRet (0 ! cnts[1]);}else {bRet cnts[0];}m_sta.pop();m_sta.push(bRet ? t : f);continue;}m_sta.emplace(ch);}return t m_sta.top();}stackchar m_sta;
};
单元测试
templateclass T1,class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1 , t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i 0; i vv1.size(); i){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{string expression;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){expression (|(f));auto res Solution().parseBoolExpr(expression);AssertEx(false,res);}TEST_METHOD(TestMethod1){expression |(f,f,f,t);auto res Solution().parseBoolExpr(expression);AssertEx(true, res);}TEST_METHOD(TestMethod2){expression !((f,t));auto res Solution().parseBoolExpr(expression);AssertEx(true, res);}};
}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
