内容简介:给定一个String类型的布尔表达式表达式可以是:
本文是LeetCode 1106. Parsing A Boolean Expression 的题解。
题意
给定一个String类型的布尔表达式 expression
,返回一个求值的结果。
表达式可以是:
-
"t", 表示为True; -
"f", 表示为False; -
"!(expr)", 将内部的expr结果取反; -
"&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与; -
"|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。
题解
直接递归解释表达式就好,每层负责解释上述的一个规则就可以。
这儿有一个优化点:实现表达式惰性求值。
代码
/**
* 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
}
}
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
HEX CMYK 转换工具
HEX CMYK 互转工具
HSV CMYK 转换工具
HSV CMYK互换工具