1106. Parsing A Boolean Expression

Return the result of evaluating a given boolean `expression`, represented as a string.

An expression can either be:

• `"t"`, evaluating to `True`;
• `"f"`, evaluating to `False`;
• `"!(expr)"`, evaluating to the logical NOT of the inner expression `expr`;
• `"&(expr1,expr2,...)"`, evaluating to the logical AND of 2 or more inner expressions `expr1, expr2, ...`;
• `"|(expr1,expr2,...)"`, evaluating to the logical OR of 2 or more inner expressions `expr1, expr2, ...`

Example 1:

``````Input: expression = "!(f)"
Output: true
``````

Example 2:

``````Input: expression = "|(f,t)"
Output: true
``````

Example 3:

``````Input: expression = "&(t,f)"
Output: false
``````

Example 4:

``````Input: expression = "|(&(t,f,t),!(t))"
Output: false
``````

Constraints:

• `1 <= expression.length <= 20000`
• `expression[i]` consists of characters in `{'(', ')', '&', '|', '!', 't', 'f', ','}`.
• `expression` is a valid expression representing a boolean, as given in the description.

``````class Solution {
public:
bool parseBoolExpr(string expression) {
stack<char> st;
for (int i = 0; i < expression.size(); ++i) {
char c = expression[i];
if (c == ')') {
unordered_set<char> seen;
while (!st.empty() && st.top() != '(') {
seen.insert(st.top()); st.pop();
}
st.pop();
char op = st.top(); st.pop();
if (op == '&') {
st.push(seen.count('f') ? 'f' : 't');
} else if (op == '|') {
st.push(seen.count('t') ? 't' : 'f');
} else {
st.push(seen.count('t') ? 'f' : 't');
}
} else if (c != ',') {
st.push(c);
}
}
return st.top() == 't';
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1106

https://leetcode.com/problems/parsing-a-boolean-expression/

https://leetcode.com/problems/parsing-a-boolean-expression/discuss/323307/Python-Easy-1-line-Cheat

https://leetcode.com/problems/parsing-a-boolean-expression/discuss/323532/JavaPython-3-Iterative-and-recursive-solutions-w-explanation-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation