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, в соответствии с предложениями Пола Макгуайра.

Чтобы получить вывод в формате вложенного списка:

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

Регулярное выражение пытается соответствовать как можно большему количеству текста, тем самым поглощая всю вашу строку.Он не ищет дополнительных соответствий регулярного выражения в частях этой строки.Вот почему вы получаете только один ответ.

Решение состоит в том, чтобы не использовать регулярные выражения.Если вы на самом деле пытаетесь разобрать математические выражения, используйте реальные решения для разбора.Если вы действительно хотите захватить части в скобках, просто зацикливайтесь на счетчиках символов, когда видите (и), и увеличивайте счетчик на единицу.

Answer 4

Языки регулярных выражений недостаточно мощны для сопоставления произвольно вложенных конструкций.Для этого вам понадобится автомат нажатия (то есть, парсер).Существует несколько таких инструментов, таких как 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 5

Стек - лучший инструмент для работы: -

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

Answer 6

Из связанного ответа:

Из конвертируемой утилиты LilyPond (и написано / защищено авторским правом, так что я могу показать это здесь):

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.

Да, он выходит из строя после заданного предела, но возможность просто подключить его к регулярным выражениям по-прежнему превосходит «правильные» альтернативы, поддерживающие неограниченную глубину практического использования.

Answer 7

Сбалансированные пары (например, в скобках) - это пример языка, который не распознается регулярными выражениями.

Ниже приводится краткое объяснение математики, почему это так.

Регулярные выражения - это способ определения конечных автоматов (сокращенно FSM). Такое устройство имеет конечное количество возможных состояний для хранения информации. То, как можно использовать это состояние, не имеет особых ограничений, но это означает, что существует абсолютное максимальное количество различных позиций, которые оно может распознать.

Например, состояние можно использовать для подсчета, скажем, несоответствующих левых скобок. Но поскольку количество состояний для этого вида подсчета должно быть полностью ограничено, то данный FSM может рассчитывать максимум до n -1, где n - это число состояний FSM может входить. Если n , скажем, 10, то максимальное число непропаренных левых скобок, которые может сопоставить FSM, равно 10, пока оно не сломается. Поскольку вполне возможно иметь еще одну левую скобку, не существует FSM, который может правильно распознать полный язык соответствующих скобок.

И что? Предположим, вы просто выбрали действительно большой n ? Проблема состоит в том, что в качестве способа описания FSM регулярные выражения в основном описывают все переходы из одного состояния в другое. Поскольку для любого N для автомата FSM потребовалось бы 2 перехода состояний (один для сопоставления левой круглой скобки и один для сопоставления правого), само регулярное выражение должно расти как минимум на постоянный коэффициент, кратный n

Для сравнения, следующий лучший класс языков (контекстно-свободные грамматики) может решить эту проблему совершенно компактным способом. Вот пример в БНФ

<em>expression</em> ::= `<strong>(</strong>` <em>expression</em> `<strong>)</strong>` <em>expression</em><br /> | <em>nothing</em><br />

Answer 8

Мое решение таково: определите функцию для извлечения содержимого в самых внешних скобках, а затем вы будете вызывать эту функцию несколько раз, пока не получите содержимое в самых внутренних скобках.

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

Answer 9

Вот демоверсия к вашему вопросу, хотя она неуклюжа, пока работает

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 = '\)\]\}')

Answer 10

Многие посты предполагают, что для вложенных фигурных скобок REGEX НЕ СПОСОБ ДЕЛАТЬ ЭТОПРОСТО СЧИТАЙТЕ ВРЕМЯ: Например, см .: Регулярное выражение для обнаружения завершенных точек с запятой C ++ для циклов & while

Вот полный пример Python для итерации по строке и подсчета скобок:

# decided for nested braces to not use regex but brace-counting
import re, string

texta = r'''
nonexistent.\note{Richard Dawkins, \textit{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.\note{Zheng Wu, \textit{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,''
\textit{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'\note',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,'\n', ' ') # replace new line with space
    print result