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, ...求或。

题解

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

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

代码

/**
 * 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
    }
}