在RegEx中创建第n级嵌套模式的算法

在RegEx中创建第n级嵌套模式的算法

您可以从理论上更仔细地考虑：嵌套

n

深度较深的括号匹配是围绕

n-1

深度小于或等于（至少一个正好

n-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 + 6l[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]

。这种形式的递归关系具有二次解，因此仅

O(n^2)

。好多了。

（对于其他人，我以前的定义

Y[n]

是

Y[n] = Y[n-1] |X[n]

；这种额外的递归意味着

X

正则表达式的长度为

O(2.41^n)

，这很糟糕。）

（的新定义

Y

是一个诱人的暗示，即甚至可能存在一种

X

线性的书写方式

n

。我不知道，而且我觉得

X

确切长度的额外限制意味着这是不可能的。）

---

以下是一些计算上述正则表达式的Python代码，您可以将其转换为javascript，而不会带来太多麻烦。

# abbreviation for the No Parenthesis regexnp = "[^()]*"# 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]