是否可以在不使用递归或平衡组的情况下将嵌套括号与正则表达式匹配？

Question

StackOverflow鼓励自己回答问题,所以我决定创建这篇文章来分享我最近发现的东西.

问题:在正则表达式中匹配任意嵌套的括号组,例如Java的java.util.regex,既不支持递归也不支持平衡组.即,匹配3个外部组:

(第一第二第三)))))))

这个练习纯粹是学术性的,因为我们都知道正则表达式不应该被用来匹配这些东西,正如Q-tips不应该被用来清理耳朵一样.

Answer 1

确实!可以使用前向引用:

(?=\()(?:(?=.*?\((?!.*?\1)(.*\)(?!.*\2).*))(?=.*?\)(?!.*?\2)(.*)).)+?.*?(?=\1)[^(]*(?=\2$)

证明

等瞧 ; 它就是.在那里,从头到尾匹配一组完整的嵌套括号.每次匹配必须捕获并保存两个子串; 这对你没用.只关注主要比赛的结果.

不,深度没有限制.不,那里没有隐藏的递归结构.只是简单的'lookarounds,带有前瞻性的参考.如果你的味道不支持前向引用(我在看你,JavaScript),那我很抱歉.我真的是.我希望我能帮助你,但我不是一个奇迹怪异的奇迹工作者.

这很好,但我想要匹配内部团体!

好的,这是交易.我们能够匹配这些外部组的原因是因为它们不重叠.一旦我们想要的比赛开始重叠,我们必须稍微调整我们的策略.我们仍然可以检查主题是否正确平衡括号组.但是,我们需要使用捕获组来保存它们,而不是直接匹配它们:

(?=\()(?=((?:(?=.*?\((?!.*?\2)(.*\)(?!.*\3).*))(?=.*?\)(?!.*?\3)(.*)).)+?.*?(?=\2)[^(]*(?=\3$))) 

与前一个表达式完全相同,除了我将它的大部分包装在一个预测中以避免消耗字符,添加一个捕获组,并调整反向引用索引以便它们与新朋友一起玩得很好.现在表达式匹配在下一个括号组之前的位置,并且感兴趣的子字符串保存为\ 1.

那么......这到底是怎么回事呢？

我很高兴你问.一般方法非常简单:一次迭代一个字符,同时匹配下一次出现的'('和')',在每种情况下捕获字符串的其余部分,以便建立从中继续搜索的位置.下一次迭代.让我一块一块地分解:

结论

所以你有它.使用前向引用和标准(扩展)正则表达式功能匹配平衡嵌套结构的方法 - 无递归或平衡组.它效率不高,而且肯定不漂亮,但它是可能的.而且以前从未做过.对我来说,这非常令人兴奋.

我知道很多人使用正则表达式来完成并帮助其他用户完成更简单和更实际的任务,但如果有人与我分享我对用正则表达式推动可能性极限的兴奋那么我很乐意听到你的消息.如果有兴趣,我还有其他类似材料可以发布.

Answer 2

简要

输入更正

首先,您的输入不正确,因为有一个额外的括号(如下所示)

(F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
                                ^

对包含或排除附加括号进行适当的修改,最终可能会出现以下字符串之一:

删除了额外的括号

(F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third)))))))
                                ^

添加了附加括号以匹配额外的右括号

((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
^

正则表达式功能

其次,这实际上只有在包含递归功能的正则表达式中才真正可行,因为任何其他方法都不能正确匹配开/关括号(如OP的解决方案中所见,它匹配来自错误输入的额外括号,如上所述).

这意味着,对于那些不口味正则表达式目前在正则表达式支持递归(使用Java,Python,JavaScript等),递归(或企图模仿递归)是不是可能.

输入

考虑到原始输入实际上是无效的,我们将使用以下输入进行测试.

(F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))
(F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third)))))))
((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third)))))))

针对这些输入进行测试应产生以下结果:

1. 无效(不匹配)
2. 有效(匹配)
3. 有效(匹配)

码

有多种匹配嵌套组的方法.下面提供的解决方案都依赖于包含递归功能的正则表达式风格(例如PCRE).

请参阅此处使用的正则表达式

使用DEFINE块

(?(DEFINE)
  (?<value>[^()\r\n]+)
  (?<groupVal>(?&group)|(?&value))
  (?<group>(?&value)*\((?&groupVal)\)(?&groupVal)*)
)
^(?&group)$

注意:此正则表达式使用标志gmx

没有DEFINE块

请参阅此处使用的正则表达式

^(?<group>
  (?<value>[^()\r\n]+)*
  \((?<groupVal>(?&group)|(?&value))\)
  (?&groupVal)*
)$

注意:此正则表达式使用标志gmx

没有x修饰符(单行)

请参阅此处使用的正则表达式

^(?<group>(?<value>[^()\r\n]+)*\((?<groupVal>(?&group)|(?&value))\)(?&groupVal)*)$

没有命名(组和引用)

请参阅此处使用的正则表达式

^(([^()\r\n]+)*\(((?1)|(?2))\)(?3)*)$

注意:这是我能想到的最短的方法.

说明

我将解释最后一个正则表达式,因为它是上面所有其他正则表达式的简化和最小的例子.

• ^ 在行的开头断言位置
• (([^()\r\n]+)*\(((?1)|(?2))\)(?3)*)将以下内容捕获到捕获组1中
  • ([^()\r\n]+)*将以下内容捕获到捕获组2中
    • [^()\r\n]+匹配该组中不存在的任何字符()\r\n一次或多次
  • \((从字面上匹配左/左括号字符
  • ((?1)|(?2))将以下任一项捕获到捕获组3中
    • (?1) 递归第一个子模式(1)
    • (?2) 递归第二个子模式(2)
  • \))从字面上匹配右/右括号字符
  • (?3)* 递归第三个子模式(3)任意次数
• $ 断言该行末尾的位置