python - 递归正则表达式模式 - 在 python 中

Question

我已经在这上面坐了两天了，但仍然没有找到有效的方法。 假设我们有字符串:

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

我想要的输出:

<562947621914222412421>

好吧，递归地<>括号内可能有数据，它可以由数字和字母组成 - 但第一层仅由数字组成。 我粗体显示了我想要提取的数据。

我想用 Python 来做这个。天真的方法当然是实现一个括号堆栈(这样我就知道我是在内部括号内还是在第一级) - 但逐个字符的效率非常低。 我相信我可以使用一个很好的正则表达式模式，但我还没有想出一些可行的东西。

一些具有足够正则表达式经验的人可以提供一点帮助吗？

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

Answer 1

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)

示例:

>>> s = '<5629476219<421fsaas42f>14222<2412f2<2421savsar21>12vsaf21>412<<<142avsa1>1a24>421>421>'
>>> chars_at_level(s)
'<562947621914222412421>'

<小时/>

现在进行性能比较。尽管 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 解决方案的系统递归限制才能工作。 “天真的”解决方案仍然是最快的。

>>> t = (1000 * '<') + '1' + (1000 * '>')
>>> timeit(lambda: chars_at_level(t), number=1000)
0.1329130509998322
>>> timeit(lambda: parse(t), number=1000) # Seb's solution using re.sub
31.281542531000014
>>> timeit(lambda: regex_sub(t), number=1000) # bobble bubble's recursive regex
0.705901896999876
>>> timeit(lambda: nested_list(t), number=1000) # Ajax1234's nested list solution
1.1296931150000091

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