基于分隔符优先级的字符串重排与重组实现技术问询

问题本质是让语义相同的表达式转化为唯一标准形式，因为AND、OR操作满足交换律，不管成员顺序如何，都能通过分层排序实现等价比较。你的现有代码仅完成了拆分，缺少每层排序与重组步骤，正确流程需按优先级从高到低拆分→排序→重组：优先级 & > , > ;，先处理最内层的高优先级AND，再处理中间层的OR，最后处理外层的低优先级AND。

实现代码 #

def normalize_expression(expr):
    # 按最低优先级;拆分低优先级AND组
    and_groups = expr.split(';')
    processed_and_groups = []
    
    for group in and_groups:
        # 按,拆分OR成员
        or_members = group.split(',')
        processed_or_members = []
        
        for member in or_members:
            # 拆分高优先级AND原子项，排序后用&拼接
            atoms = sorted(member.split('&'))
            processed_or_members.append('&'.join(atoms))
        
        # OR成员排序后用,拼接
        sorted_or_str = ','.join(sorted(processed_or_members))
        processed_and_groups.append(sorted_or_str)
    
    # 低优先级AND组排序后用;拼接，返回归一化结果
    return ';'.join(sorted(processed_and_groups))

# 测试示例
example1 = "b,a;X1"
example2 = "a,b;X1"
example3 = "r1&e;X1,a"

print(normalize_expression(example1))  # 输出: a,b;X1
print(normalize_expression(example2))  # 输出: a,b;X1
print(normalize_expression(example3))  # 输出: a,X1;e&r1

# 等价表达式直接比较
print(normalize_expression(example1) == normalize_expression(example2))  # True

逻辑说明 #

1. 高优先级AND（&）处理：拆分原子项后排序，确保类似e&r1和r1&e的表达式归一为同一形式
2. OR（,）处理：对每个OR成员列表排序，确保b,a和a,b归一为同一形式
3. 低优先级AND（;）处理：对所有AND组排序，确保X1;a,b和a,b;X1归一为同一形式

处理后，所有语义等价的表达式会转化为完全相同的字符串，直接用==即可判断等价性。

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