Python实现无括号命题逻辑表达式全括号化算法求助

原代码的核心问题 #

• 嵌套层级计算逻辑仅针对含括号的输入，但目标输入是无括号表达式，导致所有字符的嵌套层级为0，后续找最外层联结词的逻辑完全失效。
• 错误地将字符索引与联结词列表索引关联，无法正确识别表达式中的完整联结词。
• 未区分单目（not）和双目联结词，也未考虑联结词优先级，无法按逻辑结构拆分表达式。

修正思路 #

1. 明确联结词规则：定义单目/双目类型及优先级（优先级越低，越晚结合，越适合作为最外层）：
   • 单目联结词：not（优先级最高，仅作用于右侧表达式）
   • 双目联结词优先级（从低到高）：if and only if < implies < or < and
2. 精准匹配联结词：遍历表达式时确保匹配完整的联结词，避免误匹配子字符串。
3. 按优先级选择最外层联结词：优先选择优先级最低的双目联结词作为拆分点；若无双目联结词，再处理单目not。
4. 递归处理子表达式：拆分后递归处理左右子表达式，最终用括号包裹结果。

修正后的代码 #

def parenthesize(expression):
    # 定义联结词：(名称, 优先级, 是否单目)，优先级越低越晚结合
    connectives = [
        ("if and only if", 1, False),
        ("implies", 2, False),
        ("or", 3, False),
        ("and", 4, False),
        ("not", 5, True)
    ]
    
    # 基础情况：单个变量，返回带括号的形式
    tokens = expression.strip().split()
    if len(tokens) == 1:
        return f"({expression})"
    
    # 遍历所有联结词，收集所有合法的出现位置
    connective_positions = []
    expr = expression.strip()
    for name, priority, is_unary in connectives:
        start_idx = 0
        while True:
            pos = expr.find(name, start_idx)
            if pos == -1:
                break
            # 确保匹配的是独立的联结词（前后为空格或字符串首尾）
            left_valid = pos == 0 or expr[pos-1] == ' '
            right_valid = pos + len(name) == len(expr) or expr[pos + len(name)] == ' '
            if left_valid and right_valid:
                connective_positions.append((priority, is_unary, name, pos))
            start_idx = pos + len(name)
    
    # 按优先级升序排序，优先处理优先级低的联结词（最外层）
    connective_positions.sort(key=lambda x: x[0])
    
    for priority, is_unary, name, pos in connective_positions:
        if is_unary:
            # 单目not只能作为最左侧的联结词
            if pos == 0:
                sub_expr = expr[len(name):].strip()
                return f"(not {parenthesize(sub_expr)})"
        else:
            # 拆分双目联结词的左右子表达式
            left_expr = expr[:pos].strip()
            right_expr = expr[pos + len(name):].strip()
            return f"({parenthesize(left_expr)} {name} {parenthesize(right_expr)})"
    
    # 兜底：输入合法的话不会走到这里
    return f"({expression})"

# 测试示例
expression = "p and q or r implies not s"
print(parenthesize(expression))

测试结果 #

输出：((p and (q or r)) implies (not s))，与预期一致。

内容的提问来源于stack exchange，提问作者Mark