regex 创建一个正则表达式,它知道最大深度为5的平衡括号

y0u0uwnf  于 2023-04-07  发布在  其他
关注(0)|答案(3)|浏览(155)

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

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

fdbelqdn

fdbelqdn1#

除非它必须是一个表达式,否则可以使用多个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层深,以\(\)结尾,用于最内部的匹配括号。
请注意,非捕获组只是为了避免在match对象中获得多个条目。由于您只查找True/False,而不是提取的字符串本身,因此它可能也适用于捕获组:r"^(\((\((\((\((\(\))*\))*\))*\))*\))+$"

hi3rlvi2

hi3rlvi22#

这里有两个解决方案,用于平衡<>,因为它更容易读取/写入:

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

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

同样,但<>替换为\(\)

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

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

我从深度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))

测试结果(Attempt This Online!):

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

ha5z0ras3#

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

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

首先,我写了一个DFA(使用ab代替括号):

si是初始状态,se是错误状态,s0s5表示当前打开了多少个括号(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))

注意,$表示那里的空字符串,+表示交替。它没有使用+表示“前面的一个或多个”,所以我在看到这个答案后,自己在这个答案的顶部写了一个短模式。

相关问题