Python:如何将嵌套括号与正则表达式匹配？

Question

我正在尝试匹配具有嵌套括号的数学表达式字符串.

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),我可以照顾那些.

为什么它不会那样做,我怎么能这样做？

Answer 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]

(手动完成换行/缩进/注释)

编辑:修改以消除不必要的Forward,根据Paul McGuire的建议.

以嵌套列表格式获取输出:

res = parens.parseString("((12 + 2) + 3)")
res.asList()

输出:

[[['12', '+', '2'], '+', '3']]

Answer 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}

Answer 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'],
  ')'],
 '',
 '']

Answer 4

正则表达式尝试尽可能多地匹配文本,从而消耗所有字符串.它不会在该字符串的某些部分上查找正则表达式的其他匹配项.这就是为什么你只得到一个答案.

解决方案是不使用正则表达式.如果您实际上正在尝试解析数学表达式,请使用真正的解析解决方案.如果你真的只想捕获括号内的碎片,只需在你看到(和)时递增字符计数并递增一个递减计数器.

Answer 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