Geek asks and answers

Algorithm for creating the n-th level of nested templates in RegEx

As explained in Can regular expressions be used to match nested patterns? , it is not possible to create a regular expression to match an arbitrary nested pattern. But is it possible to create an algorithm that will generate the regular expression of the n-th level of "nesteness"?

basically i want to replace trim(whatever)withrtrim(ltrim(whatever))

I managed to create 3 levels manually (javascript syntax):

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

Here are some test data:

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()))))))

I know that at each level [^()]*it is necessary to replace with a non-capturing group, which may contain parentheses, but I'm not sure how to generalize the algorithm for the nth level .

+3
1

: n deep - 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 + 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]. , 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 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]
+6

More articles:


All Articles