寻求适配自定义字符串cstr的反向正则表达式Python实现

核心逻辑 #

你的需求核心是从已知的字符串末尾反向匹配正则，快速判定失败，最小化高成本的字符计算量。理论上，正则对应的有限状态机反转箭头后，就能得到反向匹配的逻辑——这正是我们实现的基础：不需要全量计算字符串，从最后一个字符开始匹配，一旦某一步不匹配直接返回失败。

Python实现方案（适配cstr特性） #

因为cstr是Python实现的延迟计算字符串，我们不需要依赖现成的全量正则库（比如re），而是自己实现轻量的反向匹配器，严格控制字符计算次数。以下是分步实现方案：

1. 正则模式反向转换 #

先把原正则转换成反向匹配的模式，处理你指定的语法：

• 普通字符/Unicode字符：直接反转顺序，比如abc→cba
• 量词（*/+/?/{m,n}）：保留量词和对应元素的绑定关系，反转元素顺序，比如ab*c→c*ba
• 字符类（[]）：字符类本身不反转，比如[abc]保持[abc]，因为它匹配单个字符
• 选择分支（|）：反转每个分支的内容，比如a|bc→a|cb
• 转义字符（\w/\W/转义单个字符）：转义部分保持不变，比如\w→\w，\$→\$

2. cstr的反向字符获取适配 #

你的cstr需要支持负数索引延迟获取字符：

• 已知最后一个字符（对应索引-1），直接缓存
• 当需要获取-k（k>1）位置的字符时，才触发该位置的计算，计算后缓存避免重复开销
• 当到达字符串开头时，抛出IndexError终止匹配

示例cstr适配代码：

class Cstr:
    def __init__(self, last_char, char_fetcher):
        self._last_char = last_char
        # char_fetcher: 接收参数为从末尾数的位置（比如1对应倒数第二个字符），返回字符；超出范围抛出ValueError
        self._char_fetcher = char_fetcher
        self._cache = {-1: last_char}

    def __getitem__(self, idx):
        if idx >= 0:
            raise NotImplementedError("仅支持负数索引反向获取字符")
        if idx in self._cache:
            return self._cache[idx]
        try:
            # 转换为从末尾数的位置：比如idx=-2对应倒数第二个，即位置2
            char = self._char_fetcher(abs(idx))
            self._cache[idx] = char
            return char
        except ValueError:
            raise IndexError("已到达字符串开头")

3. 轻量反向正则匹配器实现 #

基于转换后的反向模式，从cstr的最后一个字符开始逐段匹配，一旦某一步不匹配立即返回失败，避免计算更多字符。以下是核心匹配逻辑的框架：

class ReverseRegexMatcher:
    def __init__(self, original_pattern):
        self._reversed_pattern = self._reverse_pattern(original_pattern)
        # 预解析反向模式为token列表，方便匹配时处理
        self._tokens = self._parse_pattern_to_tokens(self._reversed_pattern)

    def _reverse_pattern(self, pattern):
        """将原正则转换为反向匹配模式"""
        reversed_parts = []
        i = len(pattern) - 1
        while i >= 0:
            # 处理量词（*+?{m,n}）
            if pattern[i] in "*+?{":
                quant_part = []
                # 收集完整量词（比如{3,5}）
                while i >= 0 and pattern[i] in "*+?{}":
                    quant_part.append(pattern[i])
                    if pattern[i] == "{":
                        # 找到对应的}
                        j = i - 1
                        while j >= 0 and pattern[j] != "}":
                            quant_part.append(pattern[j])
                            j -= 1
                        quant_part.append(pattern[j])
                        i = j - 1
                        break
                    i -= 1
                # 收集量词对应的元素
                elem = pattern[i]
                if elem == "\\":
                    # 转义字符，比如\w
                    elem = pattern[i-1] + elem
                    i -= 1
                reversed_parts.append(elem)
                reversed_parts.extend(reversed(quant_part))
                i -= 1
            # 处理字符类[]
            elif pattern[i] == "[":
                # 找到对应的]
                j = i - 1
                class_part = []
                while j >= 0 and pattern[j] != "]":
                    class_part.append(pattern[j])
                    j -= 1
                class_part.append(pattern[j])
                class_part.append(pattern[i])
                reversed_parts.append("".join(reversed(class_part)))
                i = j - 1
            # 处理选择分支|
            elif pattern[i] == "|":
                reversed_parts.append("|")
                i -= 1
            # 处理转义字符
            elif pattern[i] == "\\":
                reversed_parts.append(pattern[i-1] + pattern[i])
                i -= 2
            # 普通字符
            else:
                reversed_parts.append(pattern[i])
                i -= 1
        return "".join(reversed_parts)

    def _parse_pattern_to_tokens(self, pattern):
        """将反向模式解析为token列表，比如['c', '*', 'b', 'a']"""
        tokens = []
        i = 0
        len_p = len(pattern)
        while i < len_p:
            if pattern[i] in "*+?{":
                # 收集完整量词
                quant = []
                while i < len_p and pattern[i] in "*+?{}":
                    quant.append(pattern[i])
                    if pattern[i] == "{":
                        j = i + 1
                        while j < len_p and pattern[j] != "}":
                            quant.append(pattern[j])
                            j += 1
                        quant.append(pattern[j])
                        i = j + 1
                        break
                    i += 1
                tokens.append(("quant", "".join(quant)))
            elif pattern[i] == "[":
                # 收集完整字符类
                j = i + 1
                class_str = []
                while j < len_p and pattern[j] != "]":
                    class_str.append(pattern[j])
                    j += 1
                class_str.append(pattern[j])
                tokens.append(("char_class", "[" + "".join(class_str)))
                i = j + 1
            elif pattern[i] == "|":
                tokens.append(("branch", "|"))
                i += 1
            elif pattern[i] == "\\":
                # 转义字符
                tokens.append(("escape", pattern[i:i+2]))
                i += 2
            else:
                tokens.append(("char", pattern[i]))
                i += 1
        return tokens

    def match(self, cstr):
        """从cstr末尾开始匹配反向模式，返回是否匹配"""
        token_idx = 0
        str_idx = -1
        len_tokens = len(self._tokens)

        while token_idx < len_tokens:
            token_type, token_val = self._tokens[token_idx]
            try:
                current_char = cstr[str_idx]
            except IndexError:
                # 字符串已到开头，无法继续匹配
                return False

            # 匹配单个字符/转义字符/字符类
            if token_type in ("char", "escape", "char_class"):
                if self._char_matches_token(current_char, token_type, token_val):
                    token_idx += 1
                    str_idx -= 1
                else:
                    return False
            # 处理量词
            elif token_type == "quant":
                # 量词对应的前一个token是要匹配的元素
                elem_type, elem_val = self._tokens[token_idx - 1]
                # 尽可能多匹配符合条件的字符
                match_count = 0
                while True:
                    try:
                        check_char = cstr[str_idx - match_count]
                    except IndexError:
                        break
                    if self._char_matches_token(check_char, elem_type, elem_val):
                        match_count += 1
                    else:
                        break
                # 验证量词规则
                if token_val == "+" and match_count == 0:
                    return False
                if token_val == "?" and match_count > 1:
                    return False
                if "{" in token_val:
                    # 处理{m,n}格式
                    quant_range = token_val.strip("{}").split(",")
                    min_count = int(quant_range[0]) if quant_range[0] else 0
                    max_count = int(quant_range[1]) if quant_range[1] else float("inf")
                    if not (min_count <= match_count <= max_count):
                        return False
                # 移动索引，继续匹配后续token
                token_idx += 1
                str_idx -= match_count
            # 处理选择分支（简单实现：尝试匹配两个分支）
            elif token_type == "branch":
                # 分支前的部分已经匹配，尝试匹配第一个分支后续
                branch1_idx = token_idx + 1
                branch1_str_idx = str_idx
                branch1_match = True
                while branch1_idx < len_tokens and self._tokens[branch1_idx][0] != "branch":
                    b_token_type, b_token_val = self._tokens[branch1_idx]
                    try:
                        b_char = cstr[branch1_str_idx]
                    except IndexError:
                        branch1_match = False
                        break
                    if not self._char_matches_token(b_char, b_token_type, b_token_val):
                        branch1_match = False
                        break
                    branch1_idx += 1
                    branch1_str_idx -= 1
                if branch1_match:
                    token_idx = branch1_idx
                    str_idx = branch1_str_idx
                    continue
                # 尝试匹配第二个分支
                branch2_idx = branch1_idx + 1
                branch2_str_idx = str_idx
                branch2_match = True
                while branch2_idx < len_tokens:
                    b_token_type, b_token_val = self._tokens[branch2_idx]
                    try:
                        b_char = cstr[branch2_str_idx]
                    except IndexError:
                        branch2_match = False
                        break
                    if not self._char_matches_token(b_char, b_token_type, b_token_val):
                        branch2_match = False
                        break
                    branch2_idx += 1
                    branch2_str_idx -= 1
                if branch2_match:
                    token_idx = branch2_idx
                    str_idx = branch2_str_idx
                    continue
                # 两个分支都不匹配
                return False

        # 完全匹配的话，需要确认字符串已经到开头
        try:
            cstr[str_idx - 1]
            return False
        except IndexError:
            return True

    def _char_matches_token(self, char, token_type, token_val):
        """判断字符是否匹配指定token"""
        if token_type == "char":
            return char == token_val
        elif token_type == "escape":
            if token_val == r"\w":
                return char.isalnum() or char == "_"
            elif token_val == r"\W":
                return not (char.isalnum() or char == "_")
            else:
                # 其他转义字符，比如\$
                return char == token_val[1]
        elif token_type == "char_class":
            class_str = token_val[1:-1]
            negated = class_str.startswith("^")
            if negated:
                class_str = class_str[1:]
            # 处理字符范围，比如a-z
            in_class = False
            i = 0
            len_class = len(class_str)
            while i < len_class:
                if class_str[i] == "-" and i > 0 and i < len_class - 1:
                    start = class_str[i-1]
                    end = class_str[i+1]
                    if start <= char <= end:
                        in_class = True
                        break
                    i += 2
                else:
                    if class_str[i] == char:
                        in_class = True
                        break
                    i += 1
            return in_class if not negated else not in_class
        return False

方案优势 #

• 严格控制字符计算次数：仅在需要匹配时才计算对应位置的字符，一旦匹配失败立即终止
• 完全适配cstr的延迟计算特性：不需要预先计算整个字符串
• 轻量且定制化：仅实现你需要的正则语法，没有多余的复杂特性（比如前瞻）

内容的提问来源于stack exchange，提问作者Linda Tabatha Forester