如何实现不使用?=的两个正则表达式交集求解函数？

针对仅由字符类和基础量词组成的正则表达式，我们可以通过「拆分-对齐-逐单元求交-重组」的思路实现交集计算，完全无需使用预查语法。

核心逻辑 #

两个正则的交集，本质是它们每个匹配位置上的原子单元（字符类/带量词的字符类）的交集组合。只有当两个正则的结构可对齐（比如都是固定长度的字符类序列，或量词单元位置对应），才能计算有效交集；否则交集为空。

具体实现步骤 #

1. 解析正则为原子单元列表

将输入正则拆分为独立的匹配单元，每个单元包含：

• 字符类：比如[ab]、[0-9]，单个字符视为[a]这种单字符类
• 量词：紧跟在字符类后的*、+、?、{n}、{n,}、{n,m}，无量词则视为默认{1,1}

示例解析：

• [ab][0123] → [{'char_class': '[ab]', 'quantifier': ''}, {'char_class': '[0123]', 'quantifier': ''}]
• a{2,3}[bc] → [{'char_class': '[a]', 'quantifier': '{2,3}'}, {'char_class': '[bc]', 'quantifier': ''}]

2. 对齐正则单元序列

如果两个正则拆分后的单元数量不一致，直接返回空匹配正则^$（结构无法对齐，无交集）。

3. 逐单元计算交集

3.1 字符类交集计算

先将字符类展开为完整字符集合，再求集合交集，最后重新压缩为简洁的字符类：

• 示例1：[ab]和[bc] → 集合{a,b}∩{b,c} = {b} → 结果[b]
• 示例2：[0123]和[2345] → 集合{0,1,2,3}∩{2,3,4,5} = {2,3} → 结果[23]
• 范围处理：[a-d]和[b-e] → 交集[b-d]

如果字符类交集为空，直接返回^$。

3.2 量词交集计算

先将量词统一转换为{min, max}格式（*→{0,∞}，+→{1,∞}，?→{0,1}），再取两个量词的范围交集：

• 量词交集规则：新量词的min取两者min的最大值，max取两者max的最小值
• 示例1：{2,4}和{3,5} → 交集{3,4}
• 示例2：+和* → 交集+（即{1,∞}）

如果计算后min > max，说明该单元无匹配可能，返回^$。

4. 重组结果

将所有单元的交集结果按顺序拼接，得到最终的交集正则。

伪代码实现示例 #

def regex_intersection(re1, re2):
    # 解析正则为原子单元
    units1 = parse_regex(re1)
    units2 = parse_regex(re2)
    
    # 单元数量不一致，返回空匹配
    if len(units1) != len(units2):
        return "^$"
    
    result_units = []
    for u1, u2 in zip(units1, units2):
        # 计算字符类交集
        cc_intersect = get_char_class_intersection(u1['char_class'], u2['char_class'])
        if not cc_intersect:
            return "^$"
        
        # 转换量词为范围格式
        q1_min, q1_max = convert_quantifier_to_range(u1['quantifier'])
        q2_min, q2_max = convert_quantifier_to_range(u2['quantifier'])
        
        # 计算量词交集
        q_min = max(q1_min, q2_min)
        q_max = min(q1_max, q2_max)
        if q_min > q_max:
            return "^$"
        
        # 构建结果单元
        quantifier_str = convert_range_to_quantifier(q_min, q_max)
        result_units.append(f"{cc_intersect}{quantifier_str}")
    
    return "".join(result_units)

# --- 辅助函数 ---
def parse_regex(re):
    units = []
    i = 0
    n = len(re)
    while i < n:
        # 处理字符类
        if re[i] == '[':
            j = i + 1
            while j < n and re[j] != ']':
                j += 1
            char_class = re[i:j+1]
            i = j + 1
        # 处理单个字符
        else:
            char_class = f"[{re[i]}]"
            i += 1
        
        # 处理量词
        quantifier = ''
        if i < n and re[i] in '*+?':
            quantifier = re[i]
            i += 1
        elif i < n and re[i] == '{':
            k = i + 1
            while k < n and re[k] != '}':
                k += 1
            quantifier = re[i:k+1]
            i = k + 1
        
        units.append({'char_class': char_class, 'quantifier': quantifier})
    return units

def get_char_class_intersection(cc1, cc2):
    # 展开字符类为集合
    def expand(cc):
        chars = set()
        content = cc[1:-1]
        i = 0
        while i < len(content):
            if i+2 <= len(content) and content[i+1] == '-':
                start, end = ord(content[i]), ord(content[i+2])
                chars.update(chr(c) for c in range(start, end+1))
                i += 3
            else:
                chars.add(content[i])
                i += 1
        return chars
    
    chars1 = expand(cc1)
    chars2 = expand(cc2)
    intersect = chars1 & chars2
    if not intersect:
        return ''
    
    # 压缩为简洁字符类
    sorted_chars = sorted(intersect)
    ranges = []
    current_start = current_end = sorted_chars[0]
    for c in sorted_chars[1:]:
        if ord(c) == ord(current_end)+1:
            current_end = c
        else:
            ranges.append(f"{current_start}-{current_end}" if current_start != current_end else current_start)
            current_start = current_end = c
    ranges.append(f"{current_start}-{current_end}" if current_start != current_end else current_start)
    return f"[{''.join(ranges)}]"

def convert_quantifier_to_range(q):
    INF = 10**9
    if not q:
        return (1, 1)
    elif q == '*':
        return (0, INF)
    elif q == '+':
        return (1, INF)
    elif q == '?':
        return (0, 1)
    elif q.startswith('{'):
        content = q[1:-1]
        if ',' in content:
            n, m = content.split(',')
            return (int(n), int(m) if m else INF)
        else:
            n = int(content)
            return (n, n)

def convert_range_to_quantifier(min_q, max_q):
    INF = 10**9
    if min_q == 1 and max_q == 1:
        return ''
    elif min_q == 0 and max_q == INF:
        return '*'
    elif min_q == 1 and max_q == INF:
        return '+'
    elif min_q == 0 and max_q == 1:
        return '?'
    elif min_q == max_q:
        return f"{{{min_q}}}"
    else:
        return f"{{{min_q},{max_q}}}"

测试验证 #

输入正则[ab][0123]和[bc][2345]，经过解析、逐单元求交后，最终输出[b][23]，符合预期。

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