2

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

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

或者，再举一个例子：

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

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

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

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

CCCAAABBACCCABCCAAABBBBBBACCCCCABBBABBCCAABB

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

每次重复的次数都不一样。所以A{n}B{n}行不通。

谢谢。

4

2 回答 2

2

您的问题是正则表达式无法做到的经典示例。

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) 来解决。

于 2012-09-21T08:45:51.280 回答
0

示例：括号简化

假设 O = 左括号，C = 右括号，X = 中间的某个表达式。

在某些情况下，如果左侧的 O 数量与右侧的 C 数量相同，我们只能简化。

我们仍然可以在这里使用 RegExp：

将 rx 放入一个循环中，只匹配一对 O 和一个 C，重复对前一个循环的输出进行操作，直到它完全减少/分解。

const EXAMPLES =
`
OC
OOOOCOCCOCXCC
X
OCX
OXC
OOXCC
OOXXCC
OXOXXCC
OOXCOXXCC
OXCOXC
OXXCOXXC
`;

const is = v=>null!=v;
for (let input of EXAMPLES.trim().split(/\r?\n/g)) {
    console.log('input', JSON.stringify(input));
    let replaced;
    do {
        replaced = false;
        input = input.replace(/(?:OC|O(X)C|^(O{1,99})(X{1,99}(?:O{1,99}X{1,99}){0,99})(C{1,99})$)/gm, (...m) => {
            replaced = true;
            let out, clen;
            debugger;
            console.log(' m', JSON.stringify(m));
            if (is(m[2])) {
                clen = Math.min(m[2].length, m[4].length);
                out = m[2].substr(clen) + m[3] + m[4].substr(clen);
            }
            else {
                out = m.slice(1,-2).map(v=>null==v?'':v).join('');
            }
            console.log(' replaceWith', JSON.stringify(out));
            return out;
        });
    } while (replaced);
    console.log('output', JSON.stringify(input)+'\n')
}

输出：

input "OC"
 m ["OC",null,null,null,null,0,"OC"]
 replaceWith ""
output ""

input "OOOOCOCCOCXCC"
 m ["OC",null,null,null,null,3,"OOOOCOCCOCXCC"]
 replaceWith ""
 m ["OC",null,null,null,null,5,"OOOOCOCCOCXCC"]
 replaceWith ""
 m ["OC",null,null,null,null,8,"OOOOCOCCOCXCC"]
 replaceWith ""
 m ["OC",null,null,null,null,2,"OOOCXCC"]
 replaceWith ""
 m ["OOXCC",null,"OO","X","CC",0,"OOXCC"]
 replaceWith "X"
output "X"

input "X"
output "X"

input "OCX"
 m ["OC",null,null,null,null,0,"OCX"]
 replaceWith ""
output "X"

input "OXC"
 m ["OXC","X",null,null,null,0,"OXC"]
 replaceWith "X"
output "X"

input "OOXCC"
 m ["OOXCC",null,"OO","X","CC",0,"OOXCC"]
 replaceWith "X"
output "X"

input "OOXXCC"
 m ["OOXXCC",null,"OO","XX","CC",0,"OOXXCC"]
 replaceWith "XX"
output "XX"

input "OXOXXCC"
 m ["OXOXXCC",null,"O","XOXX","CC",0,"OXOXXCC"]
 replaceWith "XOXXC"
output "XOXXC"

input "OOXCOXXCC"
 m ["OXC","X",null,null,null,1,"OOXCOXXCC"]
 replaceWith "X"
 m ["OXOXXCC",null,"O","XOXX","CC",0,"OXOXXCC"]
 replaceWith "XOXXC"
output "XOXXC"

input "OXCOXC"
 m ["OXC","X",null,null,null,0,"OXCOXC"]
 replaceWith "X"
 m ["OXC","X",null,null,null,3,"OXCOXC"]
 replaceWith "X"
output "XX"

input "OXXCOXXC"
output "OXXCOXXC"
于 2018-07-24T16:41:51.313 回答