布尔表达式求值问题（统计不同括号化方式的数量）

让我为你详细讲解布尔表达式求值问题，这是一个经典的区间动态规划应用。

问题描述
给定一个布尔表达式，由字符 'T'（true）、'F'（false）以及运算符 '&'（与）、'|'（或）、'^'（异或）组成。表达式没有括号，我们需要通过添加括号来改变运算顺序，求使得整个表达式结果为指定布尔值（true或false）的括号化方式数量。

例如：表达式 "T^F&T"：

• 如果期望结果为 true，有2种括号化方式：(T^(F&T)) 和 ((T^F)&T)
• 如果期望结果为 false，有1种括号化方式

解题思路
这是一个典型的区间DP问题，我们需要：

1. 将表达式按运算符和操作数分离
2. 定义dp[i][j][0]和dp[i][j][1]表示区间[i,j]结果为false和true的方式数
3. 根据运算符的类型进行状态转移

详细解题步骤

步骤1：数据预处理
首先将表达式中的操作数和运算符分离存储：

# 示例表达式 "T|F&T^F"
operands = ['T', 'F', 'T', 'F']  # 操作数序列
operators = ['|', '&', '^']      # 运算符序列

步骤2：状态定义
定义三维DP数组：

• dp[i][j][0]：区间[i,j]结果为false的括号化方式数量
• dp[i][j][1]：区间[i,j]结果为true的括号化方式数量

其中i,j表示操作数的索引范围。

步骤3：初始化基础情况
对于长度为1的区间（单个操作数）：

for i in range(n):
    if operands[i] == 'T':
        dp[i][i][1] = 1  # 单个T，结果为true有1种方式
        dp[i][i][0] = 0  # 单个T，结果为false有0种方式
    else:  # operands[i] == 'F'
        dp[i][i][1] = 0  # 单个F，结果为true有0种方式  
        dp[i][i][0] = 1  # 单个F，结果为false有1种方式

步骤4：状态转移方程
对于区间[i,j]，我们需要枚举所有可能的分割点k，将区间分为[i,k]和[k+1,j]：

for length in range(2, n+1):        # 区间长度
    for i in range(0, n-length+1):  # 区间起点
        j = i + length - 1          # 区间终点
        
        for k in range(i, j):       # 分割点
            op = operators[k]       # 运算符
            
            left_false = dp[i][k][0]
            left_true = dp[i][k][1]
            right_false = dp[k+1][j][0] 
            right_true = dp[k+1][j][1]
            
            if op == '&':  # 与运算
                # 结果为true：左右都为true
                total_true = left_true * right_true
                # 结果为false：其他所有情况
                total_false = left_false * right_false + left_false * right_true + left_true * right_false
                
            elif op == '|':  # 或运算  
                # 结果为false：左右都为false
                total_false = left_false * right_false
                # 结果为true：其他所有情况
                total_true = left_true * right_true + left_true * right_false + left_false * right_true
                
            else:  # op == '^' 异或运算
                # 结果为true：左右不同
                total_true = left_true * right_false + left_false * right_true
                # 结果为false：左右相同
                total_false = left_true * right_true + left_false * right_false
            
            dp[i][j][0] += total_false
            dp[i][j][1] += total_true

步骤5：完整算法实现

def count_boolean_parentheses(expression, desired_result):
    n = (len(expression) + 1) // 2  # 操作数个数
    
    # 分离操作数和运算符
    operands = []
    operators = []
    for i, char in enumerate(expression):
        if i % 2 == 0:
            operands.append(char)
        else:
            operators.append(char)
    
    # 初始化DP数组
    dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
    
    # 基础情况
    for i in range(n):
        if operands[i] == 'T':
            dp[i][i][1] = 1
        else:
            dp[i][i][0] = 1
    
    # 区间DP
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            for k in range(i, j):
                op = operators[k]
                
                left_false, left_true = dp[i][k][0], dp[i][k][1]
                right_false, right_true = dp[k+1][j][0], dp[k+1][j][1]
                
                if op == '&':
                    total_true = left_true * right_true
                    total_false = (left_false * right_false + 
                                 left_false * right_true + 
                                 left_true * right_false)
                elif op == '|':
                    total_false = left_false * right_false
                    total_true = (left_true * right_true + 
                                left_true * right_false + 
                                left_false * right_true)
                else:  # '^'
                    total_true = left_true * right_false + left_false * right_true
                    total_false = left_true * right_true + left_false * right_false
                
                dp[i][j][0] += total_false
                dp[i][j][1] += total_true
    
    return dp[0][n-1][desired_result]

# 示例
expression = "T^F|F"
result_true = count_boolean_parentheses(expression, 1)  # 结果为true的方式数
result_false = count_boolean_parentheses(expression, 0) # 结果为false的方式数

步骤6：复杂度分析

• 时间复杂度：O(n³)，需要三层循环
• 空间复杂度：O(n²)，用于存储DP表

实际例子演示
以表达式 "T|F&T" 为例：

• 操作数: ['T', 'F', 'T']
• 运算符: ['|', '&']

计算过程：

1. 初始化：dp[0][0]=[0,1], dp[1][1]=[1,0], dp[2][2]=[0,1]
2. 长度2区间：
   • [0,1]: T|F → 运算符'|'
     • true: 1×0 + 1×1 + 0×0 = 1
     • false: 0×1 = 0
   • [1,2]: F&T → 运算符'&'
     • true: 0×1 = 0
     • false: 1×0 + 1×1 + 0×0 = 1
3. 长度3区间：[0,2]: (T|F)&T
   • 分割点k=0: (T)|(F&T)
     • 左边[0,0]: [0,1], 右边[1,2]: [1,0]
     • 运算符'|': true=1, false=0
   • 分割点k=1: (T|F)&(T)
     • 左边[0,1]: [0,1], 右边[2,2]: [0,1]
     • 运算符'&': true=1×1=1, false=1×0+0×1+0×0=0
   • 总计: true=0+1=1, false=0+0=0

这个问题的关键在于理解不同运算符的真值表，并通过区间分割来统计所有可能的括号化方式。