python中递归的Regex模式

Question

我已经坐了两天了，还是没有找到一个有效的方法。 假设我们有字符串：

<5629476219<421fsaas42f>14222<2412f2<2421savsar21>12vsaf21>412<<<142avsa1>1a24>421>421>

我想要的输出：

<562947621914222412421>

嗯，递归地说，括号内可能有数据，它可以由数字和字母组成，但第一级只包含数字。 我用粗体标出了要提取的数据。在

我想用Python来做这个。当然，最简单的方法是实现一个括号堆栈（这样我就知道我是在一个内括号内还是在第1级），但是逐字符执行效率很低。 我相信有一个很好的正则表达式模式可以使用，但我还没有想出一个有效的方法。在

一些有足够经验的正则表达式能给点帮助吗？在

当然，除了逐字符迭代运行之外，其他的想法也很受欢迎，运行时对我来说很重要。在

Answer 1

有一个alternative regex module available in Python允许recursive patterns。在

这样，您可以使用such pattern for balanced brackets并替换为空字符串。在

regex.sub(r'(?!^)<(?:[^><]*|(?R))+>', '', s)

See this regex101 demo或Python demo，结果是

<562947621914222412421>

在(?R)处，模式从一开始就被粘贴，就像(?0)一样。用^{}省略first<

Answer 2

Of course, other ideas except running char by char iteratively are welcome as well, run-time is important to me.

当然，任何正则表达式也必须逐个字符地遍历字符串。不要轻易排除“幼稚”的解决方案：事实证明，这个简单的方法比目前发布的三个答案都有效。在

---

这里有一个类似“天真”的解决方案：但它不需要堆栈，因为只有一种左括号。即使有多种类型的方括号，如果还想检测括号何时不匹配，也只需要一个堆栈。在

def chars_at_level(s):
    out = ['<']
    nesting_level = 0

    for c in s:
        if c == '<':
            nesting_level += 1
        elif c == '>':
            nesting_level -= 1
        elif nesting_level == 1:
            out.append(c)

    out.append('>')
    return ''.join(out)

示例：

^{pr2}$

---

现在进行性能比较。它胜过其他三种解决方案，尽管Seb的解决方案很接近。在

>>> timeit(lambda: chars_at_level(s))
7.594452977000401
>>> timeit(lambda: parse(s)) # Seb's solution using re.sub
7.817124693000096
>>> timeit(lambda: regex_sub(s)) # bobble bubble's recursive regex
9.322779934999744
>>> timeit(lambda: nested_list(s)) # Ajax1234's nested list solution
17.795835303999866

然而，在最坏的情况下，Seb的解决方案在诸如<<<<<<1>>>>>>这样的字符串上的效率要低得多，因为它对长度为O（n）的字符串进行O（n）替换，因此运行时间为O（n²）。另外两个发布的解决方案似乎仍然是关于这种字符串的O（n），尽管我必须增加Ajax1234解决方案的系统递归限制。“天真”的解决方案仍然是最快的。在

^{4}$

顺便说一句，即使您确实想用堆栈来扩充“天真”的解决方案，它仍然只需要O（n）时间。更改此算法以获得任何其他嵌套级别的字符也相当简单。在

Answer 3

这是一种方法；它递归地删除内部完整标记<[^<>]*>，直到只剩下外部级别的元素：

def parse(string):
    while True:
        output = re.sub(r'(?<!^)<([^<>]*)>(?!$)', '', string)
        if output == string:
            break
        string = output
    return output

^{pr2}$

>>> %timeit parse(string)
6.57 µs ± 99.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

还应该有一种方法在regex本身中进行递归，但我不能完全使它工作。内置模块re不支持此功能，但^{}支持。Here是关于这个的一些想法。在