<blockquote>
<p>Of course, other ideas except running char by char iteratively are welcome as well, run-time is important to me.</p>
</blockquote>
<p>当然,任何正则表达式也必须逐个字符地遍历字符串。不要轻易排除“幼稚”的解决方案:事实证明,这个简单的方法比目前发布的三个答案都有效。在</p>
<hr/>
<p>这里有一个类似“天真”的解决方案:但它不需要堆栈,因为只有一种左括号。即使有多种类型的方括号,如果还想检测括号何时不匹配,也只需要一个堆栈。在</p>
<pre class="lang-py prettyprint-override"><code>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)
</code></pre>
<p>示例:</p>
^{pr2}$
<hr/>
<p>现在进行性能比较。它胜过其他三种解决方案,尽管Seb的解决方案很接近。在</p>
<pre class="lang-py prettyprint-override"><code>>>> 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
</code></pre>
<p>然而,在最坏的情况下,Seb的解决方案在诸如<code><<<<<<1>>>>>></code>这样的字符串上的效率要低得多,因为它对长度为O(<em>n</em>)的字符串进行O(<em>n</em>)替换,因此运行时间为O(<em>n</em>²)。另外两个发布的解决方案似乎仍然是关于这种字符串的O(<em>n</em>),尽管我必须增加Ajax1234解决方案的系统递归限制。“天真”的解决方案仍然是最快的。在</p>
^{4}$
<p>顺便说一句,即使您确实想用堆栈来扩充“天真”的解决方案,它仍然只需要O(<em>n</em>)时间。更改此算法以获得任何其他嵌套级别的字符也相当简单。在</p>