Python：如何使用正则表达式匹配嵌套括号？
- 2025-01-09 08:46:00
- admin 原创
- 111
问题描述：
我正在尝试匹配具有嵌套括号的类似数学表达式的字符串。
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)，我可以处理那些。
为什么它还没有这样做？我该怎么做？
解决方案 1：
正如其他人提到的那样，正则表达式不是嵌套构造的正确方法。我将使用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']]
解决方案 2：
正在准备一个新的常规引擎模块来替换 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： http: //code.google.com/p/mrab-regex-hg/issues/detail? id=78
解决方案 3：
正则表达式语言功能不够强大，无法匹配任意嵌套结构。为此，您需要一个下推自动机（即解析器）。有几种这样的工具可用，例如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'],
')'],
'',
'']
解决方案 4：
正则表达式会尝试匹配尽可能多的文本，从而消耗掉整个字符串。它不会在该字符串的某些部分寻找正则表达式的其他匹配项。这就是为什么您只能得到一个答案。
解决方案是不使用正则表达式。如果您实际上正在尝试解析数学表达式，请使用真正的解析解决方案。如果您真的只想捕获括号内的部分，只需在看到 ( 和 ) 时循环计数字符并增加一个减少一个计数器。
解决方案 5：
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
解决方案 6：
来自链接的答案：
来自 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 表达式。
是的，它在给定的限制之后会崩溃，但将其插入正则表达式的能力仍然在可用性方面击败了支持无限深度的“正确”替代方案。
解决方案 7：
我相信这个功能可能适合您的需求，我很快就把它拼凑起来了，所以您可以随意清理一下。做嵌套时，很容易反向思考并从那里开始工作 =]
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
解决方案 8：
平衡对（例如括号）是正则表达式无法识别的语言的一个例子。
接下来我们从数学的角度来简要解释这一现象。
正则表达式是定义有限状态自动机（简称 FSM）的一种方式。这种设备具有有限数量的可能状态来存储信息。该状态的使用方式没有特别的限制，但这确实意味着它可以识别的不同位置的绝对最大数量是有限的。
例如，状态可用于计数不匹配的左括号。但由于这种计数的状态数量必须完全受限，因此给定的 FSM 最多可以计数到n -1，其中n是 FSM 可以处于的状态数。如果n为 10，则 FSM 可以匹配的最大不匹配左括号数量为 10，直到中断。由于完全有可能再有一个左括号，因此不存在能够正确识别匹配括号的完整语言的 FSM。
那又怎么样？假设你选择一个非常大的n？问题是，作为描述 FSM 的一种方式，正则表达式基本上描述了从一个状态到另一个状态的所有转换。由于对于任何 N，FSM 都需要 2 个状态转换（一个用于匹配左括号，一个用于匹配右括号），因此正则表达式本身必须至少增加n的常数倍
相比之下，下一类更好的语言（上下文无关语法）可以以完全紧凑的方式解决这个问题。以下是 BNF 中的一个例子
expression ::=(expression)` expression| nothing`
解决方案 9：
您可以使用正则表达式，但您需要自己进行递归。类似下面的方法可以解决问题（如果您只需要找到问题中提到的所有括在括号中的表达式）：
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
但是，此代码与“正确”括号不匹配。如果需要这样做，最好使用专门的解析器。
解决方案 10：
这是针对您的问题的演示，虽然它很笨拙，但它可以工作
import re s = '(((1+0)+1)+1)'
def getContectWithinBraces( x , *args , **kwargs):
ptn = r'[%(left)s]([^%(left)s%(right)s]*)[%(right)s]' %kwargs
Res = []
res = re.findall(ptn , x)
while res != []:
Res = Res + res
xx = x.replace('(%s)' %Res[-1] , '%s')
res = re.findall(ptn, xx)
print(res)
if res != []:
res[0] = res[0] %('(%s)' %Res[-1])
return Res
getContectWithinBraces(s , left='([{' , right = ')]}')
解决方案 11：
我的解决方案是：定义一个函数来提取最外层括号内的内容，然后反复调用该函数，直到得到最内层括号内的内容。
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
解决方案 12：
许多帖子都表明，对于嵌套括号，正则表达式并不是解决问题的方法。只需计算括号的数量：例如，请参阅： 用于检测以分号结尾的 C++ for 和 while 循环的正则表达式
这是一个完整的 Python 示例，用于迭代字符串并计算括号数：
# decided for nested braces to not use regex but brace-counting
import re, string
texta = r'''
nonexistent.
ote{Richard Dawkins, extit{Unweaving the Rainbow: Science, Delusion
and the Appetite for Wonder} (Boston: Houghton Mifflin Co., 1998), pp. 302, 304,
306-309.} more text and more.
This is a statistical fact, not a
guess.
ote{Zheng Wu, extit{Cohabitation: An Alternative Form
of Family Living} (Ontario, Canada: Oxford University Press,
2000), p. 149; hbox{Judith} Treas and Deirdre Giesen, ``Title
and another title,''
extit{Journal of Marriage and the Family}, February 2000,
p.,51}
more and more text.capitalize
'''
pos = 0
foundpos = 0
openBr = 0 # count open braces
while foundpos <> -1:
openBr = 0
foundpos = string.find(texta, r'
ote',pos)
# print 'foundpos',foundpos
pos = foundpos + 5
# print texta[pos]
result = ""
while foundpos > -1 and openBr >= 0:
pos = pos + 1
if texta[pos] == "{":
openBr = openBr + 1
if texta[pos] == "}":
openBr = openBr - 1
result = result + texta[pos]
result = result[:-1] # drop the last } found.
result = string.replace(result,'
', ' ') # replace new line with space
print result
