#yyds干货盘点# LeetCode程序员面试金典：布尔运算

题目：

给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。

示例 1:

输入: s = "1^0|0|1", result = 0

输出: 2

解释: 两种可能的括号方法是

1^(0|(0|1))

1^((0|0)|1)

示例 2:

输入: s = "0&0&0&1^1|0", result = 1

输出: 10

代码实现：

class Solution {
    public int countEval(String s, int result) {
        int n = s.length();
        int[][][] dp = new int[n][n][2];
        for (int i = 0; i < n; i++) {
            dp[i][i][0] = (s.charAt(i) - '0' == 0 ? 1 : 0);
            dp[i][i][1] = (s.charAt(i) - '0' == 1 ? 1 : 0);
        }
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l + (len - 1) < n; l++) {
                int r = l + (len - 1);
                for (int i = l; i <= r; i++) {
                    char c = s.charAt(i);
                    if (c == '&') {
                        dp[l][r][0] += dp[l][i - 1][0] * dp[i + 1][r][0] + dp[l][i - 1][0] * dp[i + 1][r][1] + dp[l][i - 1][1] * dp[i + 1][r][0];
                        dp[l][r][1] += dp[l][i - 1][1] * dp[i + 1][r][1];
                    }
                    if (c == '|') {
                        dp[l][r][0] += dp[l][i - 1][0] * dp[i + 1][r][0];
                        dp[l][r][1] += dp[l][i - 1][0] * dp[i + 1][r][1] + dp[l][i - 1][1] * dp[i + 1][r][0] + dp[l][i - 1][1] * dp[i + 1][r][1];
                    }
                    if (c == '^') {
                        dp[l][r][0] += dp[l][i - 1][0] * dp[i + 1][r][0] + dp[l][i - 1][1] * dp[i + 1][r][1];
                        dp[l][r][1] += dp[l][i - 1][0] * dp[i + 1][r][1] + dp[l][i - 1][1] * dp[i + 1][r][0];
                    }
                }
            }
        }
        return dp[0][n - 1][result];
    }
}