3

で説明されているように、正規表現を使用してネストされたパターンに一致させることはできますか? 、任意のネストされたパターンに一致する正規表現を作成することはできません。しかし、n 番目のレベルの「ネステネス」の正規表現を生成するアルゴリズムを作成することは可能ですか?

基本的に、私trim(whatever)はrtrim(ltrim(whatever))

私は手動で3つのレベルを作成することができました（javascript構文）：

level[1] = /\(([^()]*)\)/g
level[2] = /\(((?:[^()]*\([^()]*\))*[^()]*)\)/g
level[3] = /\(((?:(?:(?:[^()]*\([^()]*\))*[^()]*)*\((?:(?:[^()]*\([^()]*\))*[^()]*)*\))*[^()]*)\)/g

ここにいくつかのテストデータがあります:

1st(ddd) + 1st(ddd)
2nd(dd(d))
3rd(a(b) + (cd(h) + d(dfas) + zzz))
4th(a(b(c(d))))
8th(a(b(c(d(e(f(g()))))))

すべてのレベルで[^()]*、括弧を含むことができる非キャプチャ グループに置き換える必要があることはわかっていますが、n 番目のレベルのアルゴリズムを一般化する方法がわかりません...

4

1 に答える 1

6

より理論的に考えることができます: 深くネストされた括弧の一致は、深さ以下の一致 (少なくとも 1 つが正確​​に深い)nの周りのかっこです。n-1n-1

正規表現の再帰的な定義を与えることができます。X[n]正確にnレベルをネストY[n]するための正規表現であり、レベルまでのネストの任意のレベルを持つブラケットを含む文字列の正規表現であるとしますn。

X[n] = \( (Y[n-2] X[n-1])+ Y[n-2] \)

Y[n] = [^()]* ( \( Y[n-1] \) [^()]* )*

Y[0] = X[0] = [^()]*(ネストなし)およびX[1] = \([^()]*\). (非キャプチャ グループなどの詳細についてはまだ気にしていません。スペースは読みやすくするためのものです。)

これに基づいてアルゴリズムを作成するのは非常に簡単です。

これらの新しい (相互再帰的ではない) 定義からの正規表現は、はるかにゆっくりと長くなります (それらは指数ではなく多項式です)。

の長l[n]さを としX[n]、 を の長さとしL[n]ますY[n](定数項は、それぞれにハードコードされた文字です):

L[n] = 19 + L[n-1] = 19*n + L[0] = 19*n + 6

l[n] = 3 + L[n-2] + l[n-1] + 2 + L[n-2] + 2
     = 7 + 2 * L[n-2] + l[n-1]
     = -57 + 38 * n + l[n-1]

と の適切な初期条件を使用l[0]しl[1]ます。この形式の再帰関係は 2 次解を持つため、これは のみO(n^2)です。ずっといい。

Y[n](他の人にとっては、私は以前にwasの定義を持っていました。この追加の再帰は、正規表現Y[n] = Y[n-1] | X[n]の長さがwasであることを意味していました。XO(2.41^n)

( の新しい定義YはX、n.X

以下は、上記の正規表現を計算する Python コードの一部です。おそらく、あまり問題なく JavaScript に変換できます。

# abbreviation for the No Parenthesis regex
np = "[^()]*"

# compute Y[n] from Y[n-1]
def next_y(y_n1):
    return np + "(?:\(" + y_n1 + "\)" + np + ")*"

# compute X[n] from X[n-1] and Y[n-2]
def next_x(x_n1, y_n2):
    return "\((?:" + y_n2 + x_n1 + ")+" + y_n2 + "\)"

# compute [X[n], Y[n], Y[n-1]]
# (to allow us to make just one recursive call at each step)
def XY(n):
    if n == 0:
        return [np, # X[0]
                np, # Y[0]
                ""] # unused
    elif n == 1:
        return ["\([^()]*\)", # X[1]
                next_y(np),   # Y[1]
                np]           # Y[0]

    x_n1, y_n1, y_n2 = XY(n-1) # X[n-1], Y[n-1], Y[n-2]

    return [next_x(x_n1, y_n2), # X[n]
            next_y(y_n1),       # Y[n]
            y_n1]               # Y[n-1]

# wrapper around XY to compute just X[n]
def X(n):
    return XY(n)[0]

# wrapper around XY to compute just Y[n]
def Y(n):
    return XY(n)[1]
于 2012-05-04T11:08:39.540 に答える