2

ツリーに役立つNewick形式を解析する必要があります。これは、ノードを示す一連の角かっこ、コンマ、文字のように見えます。

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

または、別の例：

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

(,)要素は、同じ親を持つノードを意味します。私の目的（2つのリーフ間のパスの長さを測定するため）では、結果として、そのようなネストされた要素を探す必要があります。

だから、私の質問は、異なるシンボルを同じ回数一致させる方法ですか？

たとえば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。ただし、largeの式は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をループに入れ、1つのOと1つの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 に答える