我希望编写一个正则表达式，可以匹配任何在
()
(())
(()())
((()))
()()()
etc.
4个回答
22
所有这些声称你不能使用模式来匹配带有平衡嵌套括号的字符串的答案都是错的。 假装现代编程语言匹配的模式在病态教科书意义上被限制为“正则语言”是不切实际的。 只要允许反向引用，它们就不是正则的了。这使得现实世界的模式可以比教科书版本匹配更多，从而使它们更加实用。
匹配平衡括号的最简单模式是
匹配平衡括号的最简单模式是
\((?:[^()]*+|(?0))*\)。 但你应该永远不要写成这样，因为它过于紧凑，很难读懂。你应该总是使用/x模式，以允许空格和注释。所以像这样写：m{
\( # literal open paren
(?: # begin alternation group
[^()]*+ # match nonparens possessively
| # or else
(?0) # recursively match entire pattern
)* # repeat alternation group
\) # literal close paren
}x
给你的抽象概念命名并将其定义与顺序与执行解耦开来也有很多好处，这会导致以下这种情况：
my $nested_paren_rx = qr{
(?&nested_parens)
(?(DEFINE)
(?<open> \( )
(?<close> \) )
(?<nonparens> [^()] )
(?<nested_parens>
(?&open)
(?:
(?&nonparens) *+
|
(?&nested_parens)
) *
(?&close)
)
)
}x;
第二种形式现在可以方便地包含在更大的模式中。
不要让任何人告诉你不能使用模式来匹配递归定义的内容。正如我刚刚演示的，你当然可以这样做。
顺便说一下，请确保永远不要编写看起来像噪声的模式。你不需要这样做，也不应该这样做。任何禁止使用空格、注释、子程序或字母数字标识符的编程语言都无法维护。因此，在您的模式中使用所有这些东西。
当然，选择正确的语言对于这种工作是有帮助的。☺
- tchrist
8
@tchrist：如果您能指定这个示例适用的编程语言，那就太好了。当然，如果OP能说明他想要在哪些编程语言中实现这个功能，那也是很好的。 - Avi
1@avi: 我同意，因此我说了最后一句。据我所知，递归模式在Perl、PHP和PCRE中都可以使用。我使用的变量语法是针对Perl的，但这与问题有些无关。我预计，在PCRE支持递归模式之后，更多的编程语言将在未来几年内采用它们。不过要小心，因为PCRE对于头递归和尾递归的限制比Perl更多。 - tchrist
@tchrist，您的说法 "回溯引用" 使正则表达式变得不规则是不正确的。回溯引用只是很多选择的简写 -
(.)\1 只是 aa|bb|cc|dd|... 的简写，您可以对所有使用回溯引用的情况进行相同的转换。实际上，[...] 表示法和 ? 表示法都只是经典正则表达式中的选择的简写。另一方面，递归正则表达式是一种非常不同的问题，使用该特性会使其不规则... - tobyodavies考虑模式
(.+).*\1。这需要比自动机状态所需的辅助存储更多的存储空间，实际上它需要与匹配的输入字符串长度成比例的存储空间。这显然违反了ʀᴇɢᴜʟᴀʀ语言的基本属性之一，因此不能通过DFA解决，因为不能要求进一步的存储，特别是不能要求与输入长度成比例的存储。因此，该模式描述的语言根据定义不是ʀᴇɢᴜʟᴀʀ。 - tchrist@tchrist，没错，但仅凭反向引用就远远达不到无上下文的程度...因为它仍然无法匹配
S ::= '(' S ')'。我很想看看是否有人已经写了一篇关于正则表达式可以解析哪类语言的分析文章...(我仍然不认为递归正则表达式是一个“正常”的特性...我真的没有看到它们在这篇文章之外被使用过) - tobyodavies显示剩余3条评论
5
如果你遇到了不支持递归匹配的正则表达式语法，我会给你提供一个简单的Javascript实现，你可以根据自己选择的语言进行编写：
function testBraces(s) {
for (var i=0, j=0; i<s.length && j>=0; i++)
switch(s.charAt(i)) {
case '(': { j++ ; break; }
case ')': { j-- ; break; }
}
return j == 0;
}
在这里，您可以与它互动：http://jsfiddle.net/BFsn2/
（提示：此链接可供使用）- Marko Dumic
5
真实的情况是，
j不应该降到零以下，因为它表示不平衡。 - Marko Dumic我才注意到for循环的结束条件中有
&& j>=0这一部分（它一直在那里还是你在五分钟内进行了编辑？）。太好了。 - Tim Pietzcker@Tim：它从一开始就在那里，就像演示中的那样（在jsFiddle上）。 - Marko Dumic
这个答案也是错误的：现代编程语言中的模式完全能胜任工作。 - tchrist
3我之前不知道有些正则表达式版本支持递归模式匹配，因为在我使用的语言中并没有这个功能。而且大多数时候（即在我雇主的项目中），我不能选择我要使用的语言。不过，我已经修正了我的答案。 - Marko Dumic
4
这样的嵌套结构无法有效地通过正则表达式处理。您需要的是语法和该语法的解析器。在您的情况下，语法足够简单。如果您正在使用Python，请尝试使用pyparsing或funcparserlib。
使用pyparsing，您可以执行以下操作：
from pyparsing import nestedExpr
nestedExpr().parseString( "(some (string you) (want) (to) test)" ).asList()
这将返回一个包含嵌套字符串解析组件的列表。nestedExpr的默认分隔符是括号，因此您不需要额外操作。如果您想使用funcpasrerlib，可以尝试以下操作。
from funcparserlib.parser import forward_decl, many, a
bracketed = forward_decl()
bracketed.define(a('(') + many(bracketed) + a(')'))
在此之后，您可以调用
bracketed.parse( "( (some) ((test) (string) (you) (want)) (to test))" )
并且它将以元组的形式返回解析后的元素。
- srean
4
1这是另一个错误的答案。仅仅因为Python无法进行必要的复杂模式匹配并不意味着所有其他语言都会受到类似的限制。Perl、PHP和PCRE都可以完美地处理这个问题。请看我的答案。 - tchrist
3当你添加反向引用、占有符"+"或"(?number)"语法时，它不再是一个普通的语言/表达式。它可能具有类似的语法，但这并不意味着它是同一件事情。Perl 5.10及以上版本以及我记得的话，.Net框架中的语言提供了这样的扩展功能。我认为你的模式存在一个错误，尽管我可能是错的，在那里单独注释一下。噢，我不能在那里评论。无论如何，我认为你应该将"(?0)"改为"(?1)"，因为你应该在至少匹配一个匹配的括号之后进行递归。 - srean
1不，对整个括号内的(?0)进行递归是正确的。按照写法，没有第1组可供递归。我确实测试过所有这些。真的！我更喜欢使用命名组作为正则表达式子程序的最终版本。它更易于阅读、调试、扩展和维护。希望这可以帮到你。 - tchrist
你可能对(?0)是正确的。但如果你更喜欢可读性、可维护性、清晰度等，nestedExpr().parseString()似乎更短更容易 :), 不管是不是正确的语言。 - srean
0
祝你好运。你需要一个带有堆栈的有限状态自动机来解析这样的内容。它不能仅使用正则表达式进行解析，因为它不够强大。
- darioo
1
1你因为机械地重复那个错误的说法而被踩了一下，即模式基本上无法处理具有递归定义的语法。Perl、PCRE和PHP都可以很好地处理它们。坚持教授形式自动机理论的学校犯了一个错误，他们没有解释实际考虑因素导致许多工具使用反向引用甚至递归扩展正则表达式。 - tchrist
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 你的输入是什么（例如），
- 你想要获取什么，
- 你使用过哪些正则表达式却没有起作用？
- Hannes