含X替换的平衡括号序列判断及代码修复请求

问题描述 #

给定仅包含{、}、(、)、[、]的字符串，部分位置用X替代任意括号，需判断是否可通过替换所有X为合适括号，得到合法的括号序列。

示例 #

• 输入："{(X[X])}" → 输出：Balanced
• 输入："[{X}(X)]" → 输出：Not balanced

现有问题 #

现有基于栈的代码可处理上述示例，但对输入"([X}])"判断错误（实际应为Balanced，代码输出Not balanced）。

原代码问题分析 #

1. 可变默认参数陷阱：is_balanced函数的elements=Stack()默认参数在函数定义时创建，所有递归调用共享同一个栈，导致状态混乱。
2. X的处理逻辑错误：
   • 将X作为左括号时，错误创建新栈并丢弃原栈状态，而非基于原栈复制后添加左括号。
   • 未考虑X作为左括号时的多种可能（(/[/{），仅用X占位导致匹配逻辑混乱。
3. 匹配函数逻辑模糊：is_matching允许X匹配任意括号，未区分X作为左/右括号的不同匹配规则。

修复后的代码 #

def is_matching(opener, closer):
    # 仅判断标准括号的匹配关系
    return (opener == '(' and closer == ')') or \
           (opener == '[' and closer == ']') or \
           (opener == '{' and closer == '}')

def is_balanced(expression, stack=None, index=0):
    # 初始化栈，避免可变默认参数的共享问题
    if stack is None:
        stack = []
    
    # 遍历完所有字符后，栈为空则合法
    if index == len(expression):
        return len(stack) == 0
    
    char = expression[index]
    
    if char in '([{':
        # 左括号：复制栈并压入当前括号，递归处理后续字符
        new_stack = stack.copy()
        new_stack.append(char)
        return is_balanced(expression, new_stack, index + 1)
    
    elif char in ')]}':
        # 右括号：检查栈是否为空，且栈顶与当前括号匹配
        if not stack:
            return False
        if is_matching(stack[-1], char):
            new_stack = stack.copy()
            new_stack.pop()
            return is_balanced(expression, new_stack, index + 1)
        return False
    
    elif char == 'X':
        # 情况1：将X作为左括号，尝试所有三种可能的左括号
        for opener in '([{':
            new_stack = stack.copy()
            new_stack.append(opener)
            if is_balanced(expression, new_stack, index + 1):
                return True
        
        # 情况2：将X作为右括号，仅当栈不为空时，匹配栈顶的左括号
        if stack:
            # 获取栈顶左括号对应的右括号
            closer = {'(': ')', '[': ']', '{': '}'}[stack[-1]]
            new_stack = stack.copy()
            new_stack.pop()
            if is_balanced(expression, new_stack, index + 1):
                return True
        
        # 两种情况均不成立
        return False

# 测试示例
expression = "([X}])"

if not expression:
    print("No brackets in expression!")
elif len(expression) % 2 != 0:
    print("Not balanced")
elif is_balanced(expression):
    print("Balanced")
else:
    print("Not Balanced")

修复说明 #

1. 解决可变默认参数问题：使用stack=None并在函数内部初始化空列表，确保每次递归调用的栈状态独立。
2. 正确处理X的两种场景：
   • 作为左括号时，尝试所有三种可能的左括号，复制栈后递归，只要一种路径合法则返回True。
   • 作为右括号时，仅当栈不为空时，将X转换为与栈顶匹配的右括号，弹出栈顶后递归判断。
3. 简化栈操作：用Python列表替代自定义Stack类，更方便复制和状态管理。
4. 清晰匹配逻辑：is_matching仅处理标准括号匹配，X的特殊逻辑单独分支处理，避免混淆。

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