python - 正则表达式在文本的不同部分中匹配不同符号相同次数

Question

我需要解析对树有用的 Newick 格式。它看起来像一系列表示节点的括号、逗号和字母:

(A,B,(C,D)E)F

或者，再举一个例子:

(,(((,(,)),),))

(,) 元素表示具有相同父节点的节点。为了我的目的(测量两个叶子之间的路径长度)，我需要寻找这样的嵌套元素。

所以，我的问题是如何将不同的符号匹配相同的次数？

例如，我想匹配字符串中的 AB 模式:

CCCAAABBACCCABCCAAABBBBBBACCCCCABBBABBCCAABB

正则表达式应返回:['AABB','AB','AAABBB','AB','AB','AABB']

每次的重复次数都不一样。所以 A{n}B{n} 不起作用。

谢谢。

Answer 1

你的问题是正则表达式不能做的典型例子。

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages在“引理的使用”一节中证明了语言“a^nb^n”不是正则的(因此它不能被正则表达式识别)。

使用正则表达式，您只能为给定的最大n 创建正则表达式。但大型 n 的表达式可能需要很长时间才能计算。

PS。您的问题可以使用形式语法(http://en.wikipedia.org/wiki/Formal_grammar)或计数器自动机(http://en.wikipedia.org/wiki/Counter_automaton)来解决。