Java C++刷题leetcode1106解析布尔表达式

问题描述

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

• "t"，运算结果为 True
• "f"，运算结果为 False
• "!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
• "&(expr1,expr2,...)"，运算过程为对内部表达式 expr1, expr2等进行逻辑 与的运算（AND）
• "|(expr1,expr2,...)"，运算过程为对内部表达式 expr1, expr2等进行逻辑 或的运算（OR）

示例1：

输入：expression = "!(f)"
输出：true

示例2：

输入：expression = "|(t,f)"
输出：true

思路分析

可以用递归的方法来解决这个问题。可以看到，每一个布尔表达式都是由内部表达式或者表达式组成的。所以可以考虑先切分出每个内部表达式，对内部表达式进行计算，再根据组合方式进行整体计算。

具体的做法是，先切分出内部表达式。根据第一个字符是否是"(", "!"或者"t", "f"等来分类。"("表示需要递归计算内部表达式的值，"!"表示需要对当前内部表达式值进行取反的计算，"t"和"f"表示内部表达式值已经确定，无需再进行计算。

对内部表达式计算的方法，与上述方法类似，先根据第一个字符进行分类，递归计算后根据符号进行整体计算。

最后整体计算的时候，根据当前递归到的位置来判断是进行"|"运算还是"&"运算。

代码实现

可以用Java或C++来实现以上逻辑，下面是Java的实现代码（注意代码注释）：

class Solution {

    public boolean parseBoolExpr(String expression) {
        char[] expChars = expression.toCharArray();
        int[] idx = {0};
        return calculate(expChars, idx);
    }

    private boolean calculate(char[] chars, int[] idx) {
        // 首先判断当前表达式是由何种内部表达式构成（"(", "!", "t"或"f"）
        char operator = chars[idx[0]];
        idx[0]++;
        if (operator == 't') {
            return true;
        } else if (operator == 'f') {
            return false;
        } else if (operator == '!') {
            return !calculate(chars, idx);
        } else if (operator == '&') {
            // 递归计算每个内部表达式的值
            boolean result = true;
            boolean end = false;
            while (!end) {
                boolean subExp = calculate(chars, idx);
                result &= subExp;
                char nextChar = chars[idx[0]];
                if (nextChar == ')') {
                    end = true;
                    idx[0]++;
                } else if (nextChar == ',') {
                    idx[0]++;
                }
            }
            return result;
        } else if (operator == '|') {
            // 递归计算每个内部表达式的值
            boolean result = false;
            boolean end = false;
            while (!end) {
                boolean subExp = calculate(chars, idx);
                result |= subExp;
                char nextChar = chars[idx[0]];
                if (nextChar == ')') {
                    end = true;
                    idx[0]++;
                } else if (nextChar == ',') {
                    idx[0]++;
                }
            }
            return result;
        }
        return false;
    }
}

示例说明

以第二个示例为例，输入字符串为"|(t,f)"，调用"parseBoolExpr"方法后，实际是递归调用calculate方法，进行如下计算过程：

1. calculate('|\^'(t,f),1)
2. calculate(t,2)
3. 返回true
4. calculate(f,4)
5. 返回false
6. 返回true|false，也就是true