正则表达式 - 无限错误是什么意思？

Question

我现在正在参加一些技术面试，我们会问一个关于检查大括号是否平衡的问题（开放和关闭的数量相同，并且关闭永远不会超过其匹配的开放），要求人们编写一个小函数来验证这一点。

有几位应聘者考虑尝试使用正则表达式来解决此问题，但很快就放弃了。我决定尝试一下，看看是否有可能。我目前正在使用以下测试字符串：

通过

{(function(r){ return r; })()} {}{}{}{} {{{{}}}}

失败

}{ {{}}} {{{}}

我认为以下正则表达式将起作用 [^{}]*({[^{}]*})*[^{}]* 。想法是匹配非大括号字符，然后匹配 { 然后是非大括号字符，然后是 }，重复括号匹配，最后以任何非大括号字符结尾。

然而当我在 regexr.com 上使用它时，似乎出现了一个无限错误，我不明白为什么:

有人能解释一下到底是什么问题吗？

- Ian

---

在大多数正则表达式引擎中，{ 和 } 通常需要进行转义（在字符类外部），因为它们具有量词的含义。 - T.J. Crowder

我不认为JavaScript可以支持任意层级的嵌套。一些正则表达式的变种可以（因为它们超出了标准正则表达式），但JavaScript不能。你可以编写一个能处理（比如说）最多四层嵌套的表达式，但这需要硬编码实现。 - T.J. Crowder

有限自动机无法计数——使用一些现代的“正则表达式”机制可能可以匹配平衡的括号，但如果使用JavaScript实现，我会感到非常惊讶。 - Pointy

@Pointy在JavaScript中可以使用String.replace()，查找 { 和 } 并计数，将其作为第二个参数传递到函数中。 - xanatos

现代正则表达式引擎支持使用堆栈进行计数。在这种情况下，它将用于平衡文本。一些引擎使用递归（如Perl、PCRE等），一些使用计数（如Dot-Net）。大多数其他旧的、过时的引擎（如Java、JavaScript等）不支持此功能。总之，使用现代引擎可以测试或匹配平衡文本（任何内容）。使用您的尝试肯定无法完成此任务。 - user557597

Answer 1

您遇到了一个无限错误，因为您的正则表达式可以匹配任何文本。由于所有分组都标记为*，它们都被视为可选项（*匹配零个或多个出现）。这意味着引擎可以在模式中找到任何组的零个出现，并仍然将文本视为匹配。

考虑使用+标记至少一个组，表示“一个或多个”而不是“零个或多个”。尝试使用以下模式：

[^{}]*(\{[^{}]*\})+[^{}]*

这样，引擎就有了一定的限制，必须匹配您的模式才能被接受。

注意：当不在字符块（[]）中时，也最好转义 { 和 }。我已经在上面的模式中做了这个处理。Regexr.com似乎不关心，但某些引擎可能会在没有它们的情况下产生解析错误。

- Kevin Burdett

---

非常感谢，这很有道理。也许我需要深入了解正则表达式实现的工作原理。 - Ian

Answer 2

更新

这是你需要的正则表达式（一级）：

\{{0,1}[^\{\}]*\{[^\{\}]*\}[^\{\}]*\}{0,1}

我无法编写嵌套规则，但您可以说明需要多少级别。

解释：

| - 表示或（a|b - 匹配"a"或"b"字面意思）
^ - 表示行首（^a - 匹配任何以"a"开头的字符串，如"a taxi"、"apple" ...）
$ - 表示行尾（a$ - 匹配任何以"a"结尾的字符串，如"umbrella"）
\{ - 匹配字符："{" 字面意思
\( - 匹配字符："(" 字面意思

- Eiji

---

这个对 {hello { world } {it { is { a } nice} day}} 有效吗？这只是针对样例输入的解决方案，而不是针对一般性问题的解决方案。 - Pointy

@Pointy：啊，我明白了——我的错误。我已经纠正了这个问题，但是正则表达式不支持嵌套规则。我可以为他编写更好的规则（更多层次），但我需要知道它们的数量。 - Eiji

问题的重点不在于回答我如何实现我所尝试的内容，而更多地关注于“为什么会失败”。但还是谢谢。 - Ian