创建一个知道最大深度为 5

Question

我有一个正则表达式的问题，如果深度在 1 或 5 之间，它应该匹配，例如它应该匹配“()()()”，“((((()))))” ，“（（（）（（（（）））（））”而不匹配“（））（）”，“（（（（（（））））））”和“（x）”。 我有这个

    pattern = '^(?:\(\)|\(\((?:\(\)|[^()])*\)\)){0,5}$'
    return pattern

-waaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Answer 1

这里有两个平衡的解决方案

<

和

>

，因为这样更容易读/写：

(<>|<(<>|<(<>|<(<>|<(<>)+>)+>)+>)+>)+

(<((<((<((<((<>)+)?>)+)?>)+)?>)+)?>)+

同样，但用

<

和

>

替换为

\(

和

\)

：

(\(\)|\((\(\)|\((\(\)|\((\(\)|\((\(\))+\))+\))+\))+\))+

(\(((\(((\(((\(((\(\))+)?\))+)?\))+)?\))+)?\))+

我通过从深度 1 的模式开始构建它们，然后使用它构建深度 1 到 2 的模式，然后将其用于深度 1 到 3 的模式，依此类推，直到 5：

p = r'(<>)+'
for _ in range(4):
  # p = r'(<>|<p>)+'.replace('p', p)
    p = r'(<(p)?>)+'.replace('p', p)
pattern = p.replace('<', r'\(').replace('>', r'\)')

print(p)
print(pattern)

测试它：

import re

good = "()()()", "((((()))))", "(()((()))())"
bad = "())()", "(((((())))))", "(x)"

for s in good:
    print(re.fullmatch(pattern, s))

for s in bad:
    print(re.fullmatch(pattern, s))

测试结果（在线尝试！）：

<re.Match object; span=(0, 6), match='()()()'>
<re.Match object; span=(0, 10), match='((((()))))'>
<re.Match object; span=(0, 12), match='(()((()))())'>
None
None
None

Answer 2

除非必须是单个表达式，否则您可以使用多个 re.sub 将“()”替换为空字符串五次。如果所有括号匹配最多 5 级深，这应该导致一个空字符串：

import re

def parMatch(S):
    oc = r"\(\)"
    return not re.sub(oc,"",re.sub(oc,"",re.sub(oc,"",re.sub(oc,"",re.sub(oc,"",S)))))

输出：

tests = ["()()()", "((((()))))", "(()((()))())","())()", "(((((())))))","(x)"]
for S in tests:
    print(S,parMatch(S))

()()() True
((((())))) True
(()((()))()) True
())() False
(((((()))))) False
(x) False

显然，这种方法根本不需要正则表达式，所以它可能不完全符合您的期望

如果您需要它是单个表达式，您可以将多个非捕获组嵌套在一个重复（嵌套）模式中，期望一个起始括号，一个有效的配对重复 0-n 次，然后是一个右括号。使外部组至少可重复一次并跨越整个字符串（

^

...

$

）：

def parMatch(S):
    oc = r"^(\((?:\((?:\((?:\((?:\(\))*\))*?\))*?\))*?\))+$"
    return bool(re.match(oc,S))

重复出现的模式是

\((?:

...

)*?\)

，您将其嵌套在 5 层深处，以

\(\)

结尾，作为最里面的匹配括号。

Answer 3

较短的模式找到了与我的第一个答案不同的方式：

With <>:  (<(<(<(<(<>)*>)*>)*>)*>)+
With ():  (\((\((\((\((\(\))*\))*\))*\))*\))+

首先我写了一个 DFA（使用

a

和

b

而不是括号）：

si

是初始状态，

se

是错误状态，

s0

到

s5

告诉当前有多少个括号打开（0 到 5）。

那张图片是我进入这个DFA时由FSM2Regex创建的：

#states
si
s0
s1
s2
s3
s4
s5
se
#initial
si
#accepting
s0
#alphabet
a
b
#transitions
si:a>s1
si:b>se
s0:a>s1
s0:b>se
s1:a>s2
s1:b>s0
s2:a>s3
s2:b>s1
s3:a>s4
s3:b>s2
s4:a>s5
s4:b>s3
s5:a>se
s5:b>s4
se:a>se
se:b>se

它还给了我这个图案：

a(a(a(a(ab)*b)*b)*b)*(b+b(a(a(a(a(ab)*b)*b)*b)*b)*($+a(a(a(a(ab)*b)*b)*b)*b))

请注意，

$

表示那里的空字符串，

+

表示交替。它没有使用

+

来表示“一个或多个以前的事情”，所以我看到这个后自己在这个答案的顶部写了短模式。