1106. Parsing A Boolean Expression
A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:
- ‘t’ that evaluates to true.
- ‘f’ that evaluates to false.
- ‘!(subExpr)’ that evaluates to the logical NOT of the inner expression subExpr.
- ‘&(
s
u
b
E
x
p
r
1
subExpr_1
subExpr1,s
u
b
E
x
p
r
2
subExpr_2
subExpr2, …,s
u
b
E
x
p
r
n
subExpr_n
subExprn)’ that evaluates to the logical AND of the inner expressionss
u
b
E
x
p
r
1
subExpr_1
subExpr1,s
u
b
E
x
p
r
2
subExpr_2
subExpr2, …,s
u
b
E
x
p
r
n
subExpr_n
subExprn where n >= 1. - ‘|(
s
u
b
E
x
p
r
1
subExpr_1
subExpr1,s
u
b
E
x
p
r
2
subExpr_2
subExpr2, …,s
u
b
E
x
p
r
n
subExpr_n
subExprn)’ that evaluates to the logical OR of the inner expressionss
u
b
E
x
p
r
1
subExpr_1
subExpr1,s
u
b
E
x
p
r
2
subExpr_2
subExpr2, …,s
u
b
E
x
p
r
n
subExpr_n
subExprn where n >= 1.
Given a string expression that represents a boolean expression, return the evaluation of that expression.
It is guaranteed that the given expression is valid and follows the given rules.
Example 1:
Input: expression = “&(|(f))” Output: false Explanation: First, evaluate |(f) –> f. The expression is now “&(f)”. Then, evaluate &(f) –> f. The expression is now “f”. Finally, return false.
Example 2:
Input: expression = “|(f,f,f,t)” Output: true Explanation: The evaluation of (false OR false OR false OR true) is true.
Example 3:
Input: expression = “!(&(f,t))” Output: true Explanation: First, evaluate &(f,t) –> (false AND true) –> false –> f. The expression is now “!(f)”. Then, evaluate !(f) –> NOT false –> true. We return true.
Constraints:
-
1
<
=
e
x
p
r
e
s
s
i
o
n
.
l
e
n
g
t
h
<
=
2
∗
10
4
1 <= expression.length <= 2 * 10^4
1<=expression.length<=2∗104 - expression[i] is one following characters: ‘(’, ‘)’, ‘&’, ‘|’, ‘!’, ‘t’, ‘f’, and ‘,’.
From: LeetCode Link: 1106. Parsing A Boolean Expression
Solution:
Ideas:
use a stack; when meeting ), evaluate all t/f values before it with the previous operator !, &, or |.
Code:
bool parseBoolExpr(char* expression) {
char stack[20005];
int top = –1;
for (int i = 0; expression[i]; i++) {
char c = expression[i];
if (c == ',' || c == '(') continue;
if (c != ')') {
stack[++top] = c;
} else {
int hasT = 0, hasF = 0;
while (stack[top] == 't' || stack[top] == 'f') {
if (stack[top] == 't') hasT = 1;
else hasF = 1;
top—;
}
char op = stack[top—];
if (op == '!') {
stack[++top] = hasT ? 'f' : 't';
} else if (op == '&') {
stack[++top] = hasF ? 'f' : 't';
} else { // op == '|'
stack[++top] = hasT ? 't' : 'f';
}
}
}
return stack[top] == 't';
}
