我试图匹配一个类似于数学表达式的字符串，其中包含嵌套括号。
import re
p = re.compile('\(.+\)')
str = '(((1+0)+1)+1)'
print p.findall(s)
['(((1+0)+1)+1)']
我想让它匹配所有包含的表达式，例如(1+0), ((1+0)+1)...
即使它匹配了不想要的表达式如(((1+0)，我也可以处理。
为什么它现在没有做到这一点，我该怎么做呢？
13个回答
30
正如其他人所提到的，正则表达式不适用于嵌套结构。我将使用pyparsing给出一个基本示例：
import pyparsing # make sure you have this installed
thecontent = pyparsing.Word(pyparsing.alphanums) | '+' | '-'
parens = pyparsing.nestedExpr( '(', ')', content=thecontent)
这是一个使用示例：
>>> parens.parseString("((a + b) + c)")
输出：
( # all of str
[
( # ((a + b) + c)
[
( # (a + b)
['a', '+', 'b'], {}
), # (a + b) [closed]
'+',
'c'
], {}
) # ((a + b) + c) [closed]
], {}
) # all of str [closed]
为了以嵌套列表格式获取输出：
res = parens.parseString("((12 + 2) + 3)")
res.asList()
输出：
[[['12', '+', '2'], '+', '3']]
- phooji
3
2Pyparsing返回ParseResults对象，其repr输出与您所描述的相同。该类还支持
asList()，它将输出转换为嵌套列表。如果使用pprint.pprint打印它们，则应该得到良好的缩进输出。此外，nestedExpr方法是隐式递归的，因此在这种情况下，您可以将内容定义为仅为thecontent = (pyparsing.Word(pyparsing.alphanums) | '+' | '-') - 无需进行Forward操作。 - PaulMcG@Paul McGuire：感谢您的澄清！您可能已经注意到，我在pyparsing方面有点生疏。 - phooji
对于像
(a + b) + (c + (d + e))这样没有公共根的表达式，此方法将失败，但是对于((a + b) + (c + (d + e)))则可以。 - norok224
有一个新的正则表达式引擎模块正在准备中，以取代Python中现有的模块。它引入了许多新功能，包括递归调用。
import regex
s = 'aaa(((1+0)+1)+1)bbb'
result = regex.search(r'''
(?<rec> #capturing group rec
\( #open parenthesis
(?: #non-capturing group
[^()]++ #anyting but parenthesis one or more times without backtracking
| #or
(?&rec) #recursive substitute of group rec
)*
\) #close parenthesis
)
''',s,flags=regex.VERBOSE)
print(result.captures('rec'))
输出：
['(1+0)', '((1+0)+1)', '(((1+0)+1)+1)']
在regex中相关的bug: http://code.google.com/p/mrab-regex-hg/issues/detail?id=78
- ovgolovin
2
3不要...又是 Perl 的“不规则正则表达式”！ - ivan_pozdeev
由于没有其他匹配需要进行，您可以使用
(?0)来引用自身。对于给定的示例，regex.findall(r'\((?:[^()]++|(?0))++\)', s)会返回['(((1+0)+1)+1)']。 - Sundeep14
正则表达式语言的能力不足以匹配任意嵌套结构。为此，您需要一个下推自动机（即解析器）。有几个这样的工具可用，例如PLY。
Python还提供了一个解析器库，可用于其自身的语法，可能适合您的需求。然而，输出非常详细，并需要一段时间来理解。如果您对此有兴趣，以下讨论尝试尽可能简单地解释这些东西。
>>> import parser, pprint
>>> pprint.pprint(parser.st2list(parser.expr('(((1+0)+1)+1)')))
[258,
[327,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[7, '('],
[320,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[7, '('],
[320,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[7,
'('],
[320,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[2,
'1']]]]],
[14,
'+'],
[315,
[316,
[317,
[318,
[2,
'0']]]]]]]]]]]]]]]],
[8,
')']]]]],
[14,
'+'],
[315,
[316,
[317,
[318,
[2,
'1']]]]]]]]]]]]]]]],
[8, ')']]]]],
[14, '+'],
[315,
[316,
[317,
[318, [2, '1']]]]]]]]]]]]]]]],
[8, ')']]]]]]]]]]]]]]]],
[4, ''],
[0, '']]
您可以使用这个简短的函数来缓解痛苦：
def shallow(ast):
if not isinstance(ast, list): return ast
if len(ast) == 2: return shallow(ast[1])
return [ast[0]] + [shallow(a) for a in ast[1:]]
>>> pprint.pprint(shallow(parser.st2list(parser.expr('(((1+0)+1)+1)'))))
[258,
[318,
'(',
[314,
[318, '(', [314, [318, '(', [314, '1', '+', '0'], ')'], '+', '1'], ')'],
'+',
'1'],
')'],
'',
'']
这些数字来自Python模块symbol和token，您可以使用它们构建一个从数字到名称的查找表：
map = dict(token.tok_name.items() + symbol.sym_name.items())
你甚至可以将这个映射整合到shallow()函数中，这样你就可以使用字符串而不是数字：
def shallow(ast):
if not isinstance(ast, list): return ast
if len(ast) == 2: return shallow(ast[1])
return [map[ast[0]]] + [shallow(a) for a in ast[1:]]
>>> pprint.pprint(shallow(parser.st2list(parser.expr('(((1+0)+1)+1)'))))
['eval_input',
['atom',
'(',
['arith_expr',
['atom',
'(',
['arith_expr',
['atom', '(', ['arith_expr', '1', '+', '0'], ')'],
'+',
'1'],
')'],
'+',
'1'],
')'],
'',
'']
- Marcelo Cantos
3
我会说PLY更适合于大型解析任务。当我真的需要模仿现有的Lex/Yacc解析器时，我发现它最有用。至于使用python内置的解析库...哼。 - phooji
@phooji：我同意。Python的解析器库绝对不是适合所有人的。 - Marcelo Cantos
不是真的，Perl正则表达式可以匹配嵌套括号: https://metacpan.org/pod/Regexp::Common。Python使用Perl正则表达式。 - Erik Aronesty
12
这个正则表达式尝试尽可能多地匹配文本，因此消耗了整个字符串。它不会在该字符串的部分中寻找正则表达式的其他匹配项。这就是为什么您只会得到一个答案。
解决方案是不使用正则表达式。如果您真的要解析数学表达式，请使用真正的解析解决方案。如果您只想捕获括号内的内容，只需循环遍历字符，在看到 ( 和 ) 时计数并增加或减少计数器即可。
- Winston Ewert
8
Stack是完成工作的最佳工具：
import re
def matches(line, opendelim='(', closedelim=')'):
stack = []
for m in re.finditer(r'[{}{}]'.format(opendelim, closedelim), line):
pos = m.start()
if line[pos-1] == '\\':
# skip escape sequence
continue
c = line[pos]
if c == opendelim:
stack.append(pos+1)
elif c == closedelim:
if len(stack) > 0:
prevpos = stack.pop()
# print("matched", prevpos, pos, line[prevpos:pos])
yield (prevpos, pos, len(stack))
else:
# error
print("encountered extraneous closing quote at pos {}: '{}'".format(pos, line[pos:] ))
pass
if len(stack) > 0:
for pos in stack:
print("expecting closing quote to match open quote starting at: '{}'"
.format(line[pos-1:]))
在客户端代码中，由于该函数编写为生成器函数，因此仅需使用for循环模式展开匹配：-
line = '(((1+0)+1)+1)'
for openpos, closepos, level in matches(line):
print(line[openpos:closepos], level)
这个测试代码在我的屏幕上输出以下内容，注意打印输出的第二个参数表示括号的深度。
1+0 2
(1+0)+1 1
((1+0)+1)+1 0
- Benny Khoo
3
以下是来自链接答案的内容：
这段文字来源于LilyPond convert-ly工具（由我编写并著作权归属于我，所以我可以在这里展示出来）：
def paren_matcher (n):
# poor man's matched paren scanning, gives up
# after n+1 levels. Matches any string with balanced
# parens inside; add the outer parens yourself if needed.
# Nongreedy.
return r"[^()]*?(?:\("*n+r"[^()]*?"+r"\)[^()]*?)*?"*n
convert-ly在其正则表达式中倾向于使用paren_matcher（25）作为括号匹配器，这对于大多数应用程序来说可能过于复杂。但是它确实用于匹配Scheme表达式。
是的，在给定限制后它会失效，但是能够将其插入正则表达式仍然比支持无限深度的“正确”替代方案在可用性方面更加优越。
- user3489112
1
这是如何工作的？它只返回第一个/最外层匹配的括号，这正确吗？所以你需要在结果上不断调用它来深入吗？也许你需要检查是否还有任何要解析的左括号，因为当没有括号时它会返回一些东西。 - nycynik
1
我相信这个函数可能适合你的需求，我很快地把它组合起来了，所以随意稍微整理一下。当进行嵌套时，很容易倒过来考虑并从那里开始工作 =]
def fn(string,endparens=False):
exp = []
idx = -1
for char in string:
if char == "(":
idx += 1
exp.append("")
elif char == ")":
idx -= 1
if idx != -1:
exp[idx] = "(" + exp[idx+1] + ")"
else:
exp[idx] += char
if endparens:
exp = ["("+val+")" for val in exp]
return exp
- Michael Gillette
2
1我很感激你的想法，使用冗长的函数提供所请求的列表确实很糟糕。如果我的答案不如@phooji有用，请原谅我，但我怀疑这里甚至不需要一个不正确的解析模块。虽然我从上面的例子和书面描述中学到了很多解析知识。 - Michael Gillette
1@pynator：我对你的评论的语义结构感到困惑，但我想我同意 :) - phooji
1
平衡的括号对（例如）是一种不能被正则表达式识别的语言的例子。
接下来简要解释一下这是为什么。
正则表达式是定义有限状态自动机（缩写为FSM）的一种方式。这样的设备有一个有限的可能状态来存储信息。它可以使用的状态并没有特别的限制，但这意味着它能够识别的不同位置的数量是绝对最大的。
例如，状态可以用于计数，比如未匹配的左括号。但是因为那种计数所需的状态量必须完全受限，所以给定的FSM只能计数到最大值n-1，其中n是FSM可以处于的状态数。如果n是10，那么FSM可以匹配的未匹配左括号的最大数量是10，直到它崩溃。由于完全有可能有一个以上的左括号，因此没有可能的FSM能够正确地识别匹配括号的完整语言。
那又怎样？假设你只选择一个非常大的n呢？问题在于，作为描述FSM的一种方式，正则表达式基本上描述了从一个状态到另一个状态的所有转换。由于对于任何N，FSM都需要2个状态转换（一个用于匹配左括号，一个用于匹配右括号），因此正则表达式本身必须至少增长一个与n成比例的常数因子。相比之下，下一个更好的语言类别（上下文无关文法）可以以完全紧凑的方式解决这个问题。以下是BNF中的一个示例：
- SingleNegationElimination
4
2你是正确的，但也是错误的 ;) 现代编程语言包括正则表达式功能，可以匹配像
L = { ww | w \in {0,1}* }这样既不是正则也不是上下文无关的东西。虽然它们不能匹配任意嵌套的匹配括号，但原因并非你所说的。 - phooji3从历史上看，正则表达式最初是用于表示有限状态机的一种方式，但随着时间的推移，正则表达式获得了很大的实用性，以至于现代大多数正则表达式的表达能力已经超越了正则语法。因此，关于有限状态机的讨论不一定与正则表达式相关。 - sawa
我们的谈话存在误解。请参考http://montreal.pm.org/tech/neil_kandalgaonkar.shtml，了解我所说的内容。 - phooji
你错了。有些语言是上下文无关语言的子集，但是正则语法无法识别它们，例如确定性上下文无关语言或可见下推语言。（更多细节请参考：http://en.wikipedia.org/wiki/Deterministic_context-free_grammar，http://en.wikipedia.org/wiki/Nested_word） - sawa
0
你可以使用正则表达式，但需要自己做递归。类似下面这样的代码可以实现目标（如果你只需要找到所有括号括起来的表达式）：
import re
def scan(p, string):
found = p.findall(string)
for substring in found:
stripped = substring[1:-1]
found.extend(scan(p, stripped))
return found
p = re.compile('\(.+\)')
string = '(((1+0)+1)+1)'
all_found = scan(p, string)
print all_found
然而，这段代码并不匹配“正确”的括号。如果您需要这样做，最好使用专门的解析器。
- Esteban Martinez
0
我的解决方案是：定义一个函数来提取最外层括号内的内容，然后重复调用该函数，直到获取到最内层括号内的内容。
def get_string_inside_outermost_parentheses(text):
content_p = re.compile(r"(?<=\().*(?=\))")
r = content_p.search(text)
return r.group()
def get_string_inside_innermost_parentheses(text):
while '(' in text:
text = get_string_inside_outermost_parentheses(text)
return text
- Marti
1
1这个函数可以实现它所说的功能，但无法处理非嵌套的括号。例如，
get_string_inside_outermost_parentheses('a(b)c(d)e') 返回 'b)c(d'。 - Bill网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接