1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
// 1106. Parsing A Boolean Expression
#include "leetcode.h"
/*
* a boolean expression is an expression that evaluates to either 'true' or
* 'false'. it can be one of the following shapes:
* - 't' that evaluates to true
* - 'f' that evaluates to false
* - '!(subExpr)' that evalutes to the logical not of the inner expression
* 'subExpr'
* - '&(subExpr1, subExpr2, ..., subExprn)' that evalutes to the logical AND of
* the inner expressions 'subExpr1, subExpr2, ..., subExprn' where 'n >= 1'
* - '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of
* the inner expressions 'subExpr1, subExpr2, ..., subExprn' where 'n >= 1'
* given a string 'expression' that represents a boolean expression, return the
* evaluation of that expression
*/
void substr(char *dst, char *src, int start, int len) {
strncpy(dst, src + start, len);
dst[len] = '\0';
}
bool parseBoolExpr(char *expression) {
int n = strlen(expression);
if (n == 1)
return expression[0] == 't';
if (expression[0] == '!') {
char sub_expr[n - 2];
substr(sub_expr, expression, 2, n - 3);
return !parseBoolExpr(sub_expr);
}
bool is_and = expression[0] == '&', ans = is_and;
int i = 2, j = 2, cnt = 0;
for (; ans == is_and && i < n; ++i) {
if (expression[i] == '(')
++cnt;
if (expression[i] == ')')
--cnt;
if (i == n - 1 || (expression[i] == ',' && !(cnt))) {
char sub_expr[i - j + 1];
substr(sub_expr, expression, j, i - 1);
if (is_and)
ans &= parseBoolExpr(sub_expr);
else
ans |= parseBoolExpr(sub_expr);
j = i + 1;
}
}
return ans;
}
int main() {
char e1[] = {"&(|(f))"}, e2[] = {"|(f,f,f,t)"}, e3[] = {"!(&(f,t))"};
printf("%d\n", parseBoolExpr(e1)); // expect: 0
printf("%d\n", parseBoolExpr(e2)); // expect: 1
printf("%d\n", parseBoolExpr(e3)); // expect: 1
}
|