Python中为数学表达式补全括号适配中缀转后缀的技术问询

Great question! Let's break this down clearly—you don't actually need to "fill in missing brackets" as a separate step (though that's possible), because there's a standard, battle-tested algorithm designed exactly for this problem. Let's cover both the optimal solution and the bracket-filling approach in case you have specific use cases for it.

This is the industry-standard approach for converting infix expressions to postfix (Reverse Polish Notation) or directly building a parse tree, invented by Dijkstra. It natively handles operator precedence, associativity, and brackets without needing to pre-fill missing parentheses.

Core Logic #

The algorithm uses an operator stack and either an output queue (for postfix) or a node stack (for parse trees) to process each token:

• Numbers/literals: Add directly to the output (or create a BinaryTree node and push to the node stack)
• Left parenthesis: Push to the operator stack
• Right parenthesis: Pop operators from the stack to the output until a left parenthesis is found (discard the left parenthesis)
• Operators: Pop all operators from the stack that have equal or higher precedence (for left-associative operators like +, -, *, /) to the output, then push the current operator to the stack
• After token traversal, pop any remaining operators from the stack to the output

Adapting to Your BinaryTree Implementation #

To build a parse tree instead of postfix notation, adjust the algorithm to store BinaryTree nodes in the stack:

Example Code Snippet #

class BinaryTree:
    def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None

    def insert_left(self, new_node):
        if self.left_child is None:
            self.left_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t

    def insert_right(self, new_node):
        if self.right_child is None:
            self.right_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.right_child = self.right_child
            self.right_child = t

def shunting_yard_to_tree(tokens):
    op_stack = []
    node_stack = []
    # Define precedence: lowest to highest
    precedence = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2}
    
    for token in tokens:
        if token.isdigit():
            node_stack.append(BinaryTree(token))
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            # Pop operators until matching left parenthesis
            while op_stack[-1] != '(':
                op = op_stack.pop()
                right_node = node_stack.pop()
                left_node = node_stack.pop()
                # Build operator node with children
                op_tree = BinaryTree(op)
                op_tree.left_child = left_node
                op_tree.right_child = right_node
                node_stack.append(op_tree)
            op_stack.pop()  # Discard the left parenthesis
        else:  # Handle operators
            while op_stack and precedence[op_stack[-1]] >= precedence[token]:
                op = op_stack.pop()
                right_node = node_stack.pop()
                left_node = node_stack.pop()
                op_tree = BinaryTree(op)
                op_tree.left_child = left_node
                op_tree.right_child = right_node
                node_stack.append(op_tree)
            op_stack.append(token)
    # Process remaining operators
    while op_stack:
        op = op_stack.pop()
        right_node = node_stack.pop()
        left_node = node_stack.pop()
        op_tree = BinaryTree(op)
        op_tree.left_child = left_node
        op_tree.right_child = right_node
        node_stack.append(op_tree)
    return node_stack[0] if node_stack else None

# Test with your example: (3+15)*2+(6-3)
tokens = ['(', '3', '+', '15', ')', '*', '2', '+', '(', '6', '-', '3', ')']
parse_tree_root = shunting_yard_to_tree(tokens)
# Add an in-order traversal function to verify it reconstructs the expression

If you have a specific requirement to convert partial-bracket expressions to fully parenthesized ones, you can use a recursive approach that wraps sub-expressions based on operator precedence:

Step-by-Step Logic #

1. Define operator precedence and associativity (e.g., left-associative for +, -, *, /)
2. Traverse the expression to find the lowest-precedence operator that's not inside existing brackets
3. Recursively add brackets to the left and right sub-expressions of this operator
4. Wrap the result in parentheses: (left_subexpr operator right_subexpr)
5. Skip redundant brackets for sub-expressions that already have matching parentheses with higher internal precedence

Example Code Snippet #

def add_missing_brackets(expr, precedence={'(':0, '+':1, '-':1, '*':2, '/':2}):
    # First handle existing inner brackets
    if expr.startswith('(') and expr.endswith(')'):
        # Verify bracket balance (simplified here)
        return f"({add_missing_brackets(expr[1:-1])})"
    
    # Find the lowest-precedence operator outside brackets
    min_precedence = float('inf')
    op_position = -1
    bracket_balance = 0
    for idx, char in enumerate(expr):
        if char == '(':
            bracket_balance += 1
        elif char == ')':
            bracket_balance -= 1
        elif bracket_balance == 0 and char in precedence:
            # Prioritize leftmost operator for left-associative ops
            if precedence[char] < min_precedence or (precedence[char] == min_precedence and op_position != -1):
                min_precedence = precedence[char]
                op_position = idx
    if op_position == -1:
        return expr  # No operators left (pure number)
    # Recursively process left and right parts
    left_part = add_missing_brackets(expr[:op_position].strip())
    right_part = add_missing_brackets(expr[op_position+1:].strip())
    return f"({left_part} {expr[op_position]} {right_part})"

# Test cases
print(add_missing_brackets("(3+15)*2+(6-3)"))  # Output: ((3+15)*2)+(6-3)
print(add_missing_brackets("3+15*2+6-3"))     # Output: (((3+(15*2))+6)-3)

• Best Practice: Use the Shunting-yard algorithm directly—it's more efficient, cleaner, and avoids the extra step of bracket-filling. It's the standard solution for infix-to-postfix or parse tree generation in compilers and calculators.
• Bracket-Filling: Only use this if you have a specific need for fully parenthesized expressions. It essentially replicates the precedence logic of Shunting-yard but adds string manipulation overhead.

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