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

Question

问题是：匹配一组任意嵌套的括号，这是一种正则表达式的风格，比如Java的Java。util。既不支持递归也不支持平衡组的正则表达式。即，匹配以下三个外部组：

（F（i（r（s）t）））（（S）（e）（（c）（o））（n）d) (((((((第三)))))))

这个练习纯粹是学术性的，因为我们都知道正则表达式不应该被用来匹配这些东西，就像Q-提示不应该被用来清洁耳朵一样。

堆栈

Answer 1

首先，您的输入不正确，因为有一个额外的括号（如下所示）

(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)
  (?<value>[^()\r\n]+)
  (?<groupVal>(?&group)|(?&value))
  (?<group>(?&value)*\((?&groupVal)\)(?&groupVal)*)
)
^(?&group)$

注意：这个正则表达式使用标志gmx

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

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

注意：这个正则表达式使用标志gmx

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

^(?<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）递归第一个子模式（1）

Answer 2

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

证据

瞧；就在那里。右边的括号从头到尾匹配一组完整的嵌套括号。每个匹配必须捕获并保存两个子串；这些对你没用。只需关注主要比赛的结果。

不，深度没有限制。不，这里没有隐藏的递归构造。只是简单的环顾四周，带有一点向前的参照。如果你的口味不支持转发引用（我在看你，JavaScript），那么我很抱歉。真的。我希望我能帮助你，但我不是一个神奇的工作者。

好吧，就这么定了。我们之所以能够匹配这些外部组，是因为它们不重叠。一旦我们想要的比赛开始重叠，我们必须稍微调整我们的策略。我们仍然可以检查主题是否有正确平衡的括号组。然而，我们不需要直接匹配它们，而是需要用这样一个捕获组来保存它们：

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

与前面的表达式完全相同，除了我已经将其中的大部分包装在一个前瞻中以避免使用字符，添加了一个捕获组，并调整了反向引用html" target="_blank">索引，以便他们与新朋友玩得很好。现在，表达式在下一个括号组之前的位置匹配，并且感兴趣的子字符串保存为\1。

很高兴你问我。一般的方法非常简单：一次遍历一个字符，同时匹配下一次出现的“（”和“）”，在每种情况下捕获字符串的其余部分，以便确定在下一次迭代中恢复搜索的位置。让我把它一块一块地分解：