时间戳

首页 > 解决方案 > 找出正则表达式满足句子的位置

python - 找出正则表达式满足句子的位置

问题描述

我有一些句子和一个正则表达式。是否有可能找出我的句子满足正则表达式的位置。例如，考虑我的句子 asMMMV和正则表达式 as M+V?T*Z+。现在正则表达式直到M+V?满足句子，正则表达式的剩余部分T*Z+应该是我的输出。

我现在的方法是将正则表达式分解为单个部分并将其存储在一个列表中，然后通过连接前 n 个部分直到句子匹配来匹配。例如，如果我的正则表达式是M+V?T*Z+，那么我的列表是['M+', 'V?', 'T*', 'Z+']。然后我首先在循环中匹配我的字符串 by M+，第二个 byM+V?依此类推，直到找到完全匹配，然后将剩余的列表作为输出。下面是代码

            re_exp = ['M+', 'V?', 'T*', 'Z+']
            for n in range(len(re_exp)):
                re_expression = ''.join(re_exp[:n+1])
                if re.match(r'{0}$'.format(re_expression), sentence_language):
                    return re_exp[n+1:]

是否有更好的方法来实现这一点可能是通过使用一些解析库等。

标签： pythonregexparsing

解决方案

假设您的正则表达式相当简单，没有组、反向引用、前瞻等，例如在您的情况下，按照 pattern \w[+*?]?，您可以先将其拆分为多个部分，就像您已经做的那样。但是，您可以通过切掉已经匹配的部分来单独测试每个部分，而不是迭代地连接这些部分并将它们与整个字符串进行匹配。

def match(pattern, string):
    res = pat = ""
    for p in re.findall(r"\w[+*?]?", pattern):
        m = re.match(p, string)
        if m:
            g = m.group()
            string = string[len(g):]
            res, pat = res + g, pat + p
        else:
            break
    return pat, res

例子：

>>> for s in "MMMV", "MMVVTTZ", "MTTZZZ", "MVZZZ", "MVTZX":
>>>     print(*match("M+V?T*Z+", s))
...
M+V?T* MMMV
M+V?T* MMV
M+V?T*Z+ MTTZZZ
M+V?T*Z+ MVZZZ
M+V?T*Z+ MVTZ

但是请注意，在最坏的情况下，有一个长度字符串n和一个n部分模式，每个只匹配一个字符，这仍然需要 O(n²) 来重复切片字符串。

此外，如果两个连续的部分大约是相同的字符，这可能会失败，例如a?a+b（应该等同于a+b）将不匹配ab，但只是aab因为单曲a已经被a?.

您可以通过为这种非常简化的正则表达式编写自己的非常简单的正则表达式匹配器来将复杂性降低到 O(n)，但在平均情况下，这可能不值得，甚至更慢。

推荐阅读