Python递归正则匹配函数多?场景匹配异常问题求助

问题背景 #

实现了一个正则风格的字符串匹配逻辑，其中?表示其前导字符可出现0次或多次。单个?场景下匹配正常，但正则表达式包含两个及以上?时出现异常，例如：

• 测试用例3：reg = "co?lou?r"，st = "color"，实际返回False，预期返回True

原代码 #

def single_character_string(a, b) -> "return True if characters match":
    """check if two characters match"""
    if len(a) == 0:
        return True
    elif len(b) == 0:
        return False
    else:
        if a == '.':
            return True
        else:
            if a == b:
                return True
            else:
                return False


def meta_question_result(temp):
    if len(temp) >= 2:
        if temp[1] == '?':
            k_1 = temp.replace(temp[0: 2], '')  # no char
            k_2 = temp.replace(temp[1], '')  # char
            return k_1, k_2


def check_pair_by_pair(template, check_string) -> "Strings are of Equal length! " \
                                                  "return True if lines are identical":
    """check if two strings match symbol by symbol. template may be less than string, the opposite
    is False"""
    if not template:  # exit from recursion
        return True
    if not check_string:  # exit from recursion
        return False
    if meta_question_result(template):
        t_1, t_2 = meta_question_result(template)
        if single_character_string(t_1[0], check_string[0]):
            return check_pair_by_pair(t_1[1:], check_string[1:])
        if single_character_string(t_2[0], check_string[0]):
            return check_pair_by_pair(t_2[1:], check_string[1:])
        else:
            return False
    elif single_character_string(template[0], check_string[0]):
        return check_pair_by_pair(template[1:], check_string[1:])
    else:
        return False

reg, st = input().split("|")
print(check_pair_by_pair(reg, st))

问题分析 #

1. meta_question_result函数逻辑错误：使用str.replace()会替换所有匹配的[字符]?子串，而非仅第一个。例如处理"co?lou?r"时，会错误地把所有"o?"都移除，导致生成的分支模板不符合预期。
2. 递归匹配逻辑缺失回溯：遇到[字符]?时，仅尝试了两种固定分支，未考虑前导字符多次出现的场景，且一旦某个分支不匹配就直接返回False，没有尝试其他可能的匹配路径。
3. 终止条件不完善：原逻辑中模板为空时直接返回True，未考虑字符串未匹配完的情况；字符串为空时直接返回False，未考虑剩余模板全是[字符]?可跳过的场景。

修复后的代码 #

def single_character_string(a, b):
    """检查单个模板字符是否匹配字符串字符，.匹配任意字符"""
    if a == '.':
        return True
    return a == b


def check_pair_by_pair(template, check_string):
    """正则风格匹配：?表示前导字符可出现0次或多次，返回是否完全匹配"""
    # 终止条件1：模板和字符串都为空，匹配成功
    if not template and not check_string:
        return True
    # 终止条件2：模板为空但字符串非空，匹配失败
    if not template:
        return False
    # 终止条件3：字符串为空，检查剩余模板是否全是x?形式（可全部跳过）
    if not check_string:
        i = 0
        while i < len(template):
            if i + 1 >= len(template) or template[i+1] != '?':
                return False
            i += 2
        return True
    
    # 处理当前字符带?的情况
    if len(template) >= 2 and template[1] == '?':
        current_char = template[0]
        # 分支1：跳过当前字符和?（出现0次）
        if check_pair_by_pair(template[2:], check_string):
            return True
        # 分支2：当前字符匹配时，尝试匹配1次并继续用原模板匹配剩余字符串（支持多次出现）
        if single_character_string(current_char, check_string[0]):
            if check_pair_by_pair(template, check_string[1:]):
                return True
        return False
    # 普通字符匹配
    if single_character_string(template[0], check_string[0]):
        return check_pair_by_pair(template[1:], check_string[1:])
    return False

# 测试案例验证
test_cases = [
    ("co?lou?r", "colour", True),
    ("co?lou?r", "clor", True),
    ("co?lou?r", "color", True),
]
for reg, st, expected in test_cases:
    result = check_pair_by_pair(reg, st)
    print(f"reg={reg}, st={st}: {result} (预期: {expected})")

# 保留原输入处理逻辑
# reg, st = input().split("|")
# print(check_pair_by_pair(reg, st))

修复说明 #

1. 移除meta_question_result函数，直接在匹配逻辑中通过切片处理[字符]?分支，避免全局替换的错误。
2. 完善递归终止条件，确保字符串完全匹配。
3. 针对?的处理增加了重复匹配分支：匹配当前字符后，继续使用原[字符]?模板匹配剩余字符串，实现前导字符可出现多次的需求。
4. 简化single_character_string函数逻辑，去除冗余的长度判断（确保调用时传入单个字符）。

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