LeetCode:1106. Parsing A Boolean Expression

本文是LeetCode 1106. Parsing A Boolean Expression的题解。

题意

给定一个String类型的布尔表达式expression,返回一个求值的结果。

表达式可以是:

  • "t", 表示为 True;
  • "f", 表示为 False;
  • "!(expr)", 将内部的 expr 结果取反;
  • "&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与;
  • "|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。

题解

直接递归解释表达式就好,每层负责解释上述的一个规则就可以。

这儿有一个优化点:实现表达式惰性求值。

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
* https://www.robberphex.com/parsing-a-boolean-expression/
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Parsing A Boolean Expression.
* Memory Usage: 38 MB, less than 100.00% of Java online submissions for Parsing A Boolean Expression.
*/
class Solution {
class Result {
/**
* 表达式结果
*/
boolean res;
/**
* 下次解析的起始位置
*/
int end;

Result(boolean res, int end) {
this.res = res;
this.end = end;
}
}

private Result parseBoolExpr(String expression, int start) {
if (expression.charAt(start) == 'f') {
return new Result(false, start + 1);
} else if (expression.charAt(start) == 't') {
return new Result(true, start + 1);
} else if (expression.charAt(start) == '!') {
Result result = parseBoolExpr(expression, start + 2);
result.res = !result.res;
result.end++;
return result;
} else if (expression.charAt(start) == '&') {
Result finalResult = new Result(true, 0), result;
start++;
do {
result = parseBoolExpr(expression, start + 1);
if (!result.res) {
// 在这儿可以实现惰性求值
finalResult.res = false;
}
start = result.end;
// 如果是逗号,继续解析
} while (expression.charAt(result.end) == ',');
finalResult.end = result.end + 1;
return finalResult;
} else if (expression.charAt(start) == '|') {
Result finalResult = new Result(false, 0), result;
start++;
do {
result = parseBoolExpr(expression, start + 1);
if (result.res) {
// 在这儿可以实现惰性求值
finalResult.res = true;
}
start = result.end;
} while (expression.charAt(result.end) == ',');
finalResult.end = result.end + 1;
return finalResult;
} else {
throw new RuntimeException();
}
}

public boolean parseBoolExpr(String expression) {
return parseBoolExpr(expression, 0).res;
}

public static void main(String[] args) {
boolean res = new Solution().parseBoolExpr("!(&(&(!(&(f)),&(t),|(f,f,t)),&(t),&(t,t,f)))");
System.out.println(res);
// 输出 true
}
}

LeetCode:1106. Parsing A Boolean Expression

https://www.robberphex.com/parsing-a-boolean-expression/

作者

Robert Lu

发布于

2019-06-30

许可协议

评论