如何移除算术表达式中的冗余括号？（基于表达式树遍历场景）

核心问题分析 #

你当前的中序遍历会给每个节点都包裹括号，导致出现((2*3))这类冗余情况——子节点本身被加了括号，父节点又套了一层。靠事后正则替换数字括号只能解决部分问题，没法区分“必要括号”和“冗余括号”，最优方案是在遍历生成字符串时就判断是否需要加括号，从根源避免冗余。

具体实现思路 #

1. 定义运算符优先级与结合性

先给常见运算符设定优先级（乘除优先级高于加减），同时考虑结合性（比如减法、除法是左结合，右子节点同优先级时需要加括号避免歧义）：

op_priority = {'+': 1, '-': 1, '*': 2, '/': 2}

2. 修改中序遍历函数，动态判断括号需求

给遍历函数增加参数，传递父节点的优先级、当前节点是左/右子节点，以此决定是否给当前节点的表达式加括号：

• 叶子节点（数字）：直接返回数字，不加括号。
• 非叶子节点：递归处理左右子节点后，对比当前节点与父节点的优先级：
  • 如果当前节点优先级低于父节点：必须加括号（比如加法作为乘法的子节点）。
  • 如果优先级相同，结合性要求加括号（比如减法的右子节点是减法，需要加括号）。
  • 其他情况：不用加括号。

修改后的示例代码：

def inorder(tree, parent_priority=0, is_left_child=True):
    if tree is None:
        return ""
    
    root_val = tree.getRootVal()
    # 叶子节点（数字）直接返回
    if not tree.getLeftChild() and not tree.getRightChild():
        return str(root_val)
    
    current_priority = op_priority[root_val]
    # 递归处理左右子节点，传递当前节点的优先级
    left_str = inorder(tree.getLeftChild(), current_priority, is_left_child=True)
    right_str = inorder(tree.getRightChild(), current_priority, is_left_child=False)
    
    need_parentheses = False
    # 当前优先级低于父节点，必须加括号
    if current_priority < parent_priority:
        need_parentheses = True
    # 优先级相同但结合性要求加括号（减法、除法的右子节点）
    elif current_priority == parent_priority:
        if root_val in ('-', '/') and not is_left_child:
            need_parentheses = True
    
    expr = f"{left_str}{root_val}{right_str}"
    # 根节点如果需要保留外层括号，直接返回带括号的；否则返回expr
    return f"({expr})" if need_parentheses else expr

3. 可选：正则替换兜底（不推荐）

如果一定要用正则补漏，可循环匹配内部无括号的括号对，重复替换直到没有冗余：

import re

def clean_redundant(s):
    # 先处理数字括号
    s = re.sub(r'\((\d+)\)', r'\1', s)
    # 循环替换嵌套的冗余括号（比如((a*b)) → (a*b)）
    pattern = r'\(([^()]+)\)'
    while re.search(pattern, s):
        s = re.sub(pattern, r'\1', s)
    # 如果需要保留整个表达式的外层括号，可手动添加
    return f"({s})"

⚠️ 注意：正则方法无法区分必要括号（比如(5-(2*3))里的括号不能删），只适合简单场景，优先用遍历判断的方法。

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