如何自动将算术式逻辑语句转换为min/max函数形式

针对嵌套逻辑语句的转换需求，推荐两种Python实现思路，均能从最内层表达式开始处理，逐步完成全嵌套结构的转换：

方法1：正则循环替换（简单高效，适合全括号场景） #

利用正则表达式循环匹配并替换最内层无嵌套的逻辑表达式，先处理implies，再依次处理and/or，直到所有运算符都完成转换：

import re

def logic_to_minmax(expr):
    # 第一步：替换implies为等价的max形式
    expr = re.sub(r'\(([^()]+) implies ([^()]+)\)', r'max(~\\1,\\2)', expr)
    
    # 循环替换最内层的AND（转min）
    while True:
        new_expr = re.sub(r'\(([^()]+) and ([^()]+)\)', r'min(\\1,\\2)', expr)
        if new_expr == expr:
            break
        expr = new_expr
    
    # 循环替换最内层的OR（转max）
    while True:
        new_expr = re.sub(r'\(([^()]+) or ([^()]+)\)', r'max(\\1,\\2)', expr)
        if new_expr == expr:
            break
        expr = new_expr
    
    return expr

# 测试示例
original_expr = "((p implies q) and (r implies s)) and (p or r)"
converted_expr = logic_to_minmax(original_expr)
print(converted_expr)  # 输出：min(min(max(~p,q),max(~r,s)),max(p,r))

工作原理 #

• [^()]+确保只匹配无嵌套括号的最内层表达式，避免干扰外层结构
• 循环替换直到没有可匹配项，保证所有嵌套层级都被处理
• 如需添加XOR等其他运算符，只需在implies替换后增加对应的正则替换规则即可

方法2：栈式解析（灵活通用，支持复杂语法） #

通过栈结构遍历字符串，遇到右括号时回溯提取当前最内层表达式，转换后重新压入栈，天然适配任意深度的嵌套：

def logic_to_minmax_stack(expr):
    # 先用临时符号替换implies，方便后续识别
    expr = expr.replace('implies', '->')
    stack = []
    
    for char in expr:
        if char != ')':
            stack.append(char)
        else:
            # 回溯提取左括号到当前右括号之间的内容
            temp = []
            while stack[-1] != '(':
                temp.append(stack.pop())
            stack.pop()  # 弹出左括号
            
            # 处理提取到的内层表达式
            sub_expr = ''.join(reversed(temp)).strip()
            if '->' in sub_expr:
                a, b = sub_expr.split('->', 1)
                converted = f'max(~{a.strip()},{b.strip()})'
            elif 'and' in sub_expr:
                a, b = sub_expr.split('and', 1)
                converted = f'min({a.strip()},{b.strip()})'
            elif 'or' in sub_expr:
                a, b = sub_expr.split('or', 1)
                converted = f'max({a.strip()},{b.strip()})'
            else:
                converted = sub_expr  # 变量或取反变量直接保留
            
            # 将转换后的内容重新压入栈
            stack.extend(list(converted))
    
    return ''.join(stack)

# 测试示例
original_expr = "((p implies q) and (r implies s)) and (p or r)"
converted_expr = logic_to_minmax_stack(original_expr)
print(converted_expr)  # 输出：min(min(max(~p,q),max(~r,s)),max(p,r))

工作原理 #

• 栈结构天然适合处理嵌套层级，每次处理最内层的括号表达式
• 可直接扩展支持更多运算符（如XOR），只需在sub_expr判断分支中添加对应转换规则
• 无需依赖正则，对格式不规范的输入容错性更强

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