Разбор вложенных скобок в Python, захват содержимого по уровню - PullRequest
Новая
       12

Разбор вложенных скобок в Python, захват содержимого по уровню

14 голосов
/ 26 ноября 2010

Видимо, эта проблема возникает довольно часто, после прочтения

Регулярного выражения для обнаружения завершенных точек с запятой C ++ для циклов & while

и обдумывания проблемы дляНекоторое время я написал функцию для возврата содержимого, содержащегося в произвольном числе nested ()

. Функцию можно легко расширить на любой объект регулярного выражения, публикуя здесь свои соображения и соображения.

любой совет по рефакторингу был бы признателен

(заметьте, я все еще новичок в Python, и мне не хотелось выяснять, как вызывать исключения или что-то в этом роде, поэтому у меня просто была функциявернуть 'fail', если он не мог понять, что происходит)

Отредактированная функция, учитывающая комментарии: 

def ParseNestedParen(string, level):
    """
    Return string contained in nested (), indexing i = level
    """
    CountLeft = len(re.findall("\(", string))
    CountRight = len(re.findall("\)", string))
    if CountLeft == CountRight:
        LeftRightIndex = [x for x in zip(
        [Left.start()+1 for Left in re.finditer('\(', string)], 
        reversed([Right.start() for Right in re.finditer('\)', string)]))]

    elif CountLeft > CountRight:
        return ParseNestedParen(string + ')', level)

    elif CountLeft < CountRight:
        return ParseNestedParen('(' + string, level)

    return string[LeftRightIndex[level][0]:LeftRightIndex[level][1]]

Ответы [ 3 ]

28 голосов
/ 26 ноября 2010

Вы не ясно даете понять, какова спецификация вашей функции, но это поведение мне кажется неправильным: 

>>> ParseNestedParen('(a)(b)(c)', 0)
['a)(b)(c']
>>> nested_paren.ParseNestedParen('(a)(b)(c)', 1)
['b']
>>> nested_paren.ParseNestedParen('(a)(b)(c)', 2)
['']

Другие комментарии к вашему коду:

  • Docstring говорит "сгенерировать", но функция возвращает список, а не генератор.
  • Поскольку возвращается только одна строка, зачем возвращать ее в список?
  • При каких обстоятельствах функция может вернуть строку fail?
  • Повторный вызов re.findall, а затем отбрасывание результата бесполезен.
  • Вы пытаетесь сбалансировать скобки в строке, но вы делаете это только по одной скобке за раз: 
>>> ParseNestedParen(')' * 1000, 1)
RuntimeError: maximum recursion depth exceeded while calling a Python object

Как сказал Томи в вопросе , который вы связали с , «регулярные выражения действительно являются неподходящим инструментом для работы!»

Обычный способ синтаксического анализа вложенных выражений - использовать стек по следующим строкам: 

def parenthetic_contents(string):
    """Generate parenthesized contents in string as pairs (level, contents)."""
    stack = []
    for i, c in enumerate(string):
        if c == '(':
            stack.append(i)
        elif c == ')' and stack:
            start = stack.pop()
            yield (len(stack), string[start + 1: i])

>>> list(parenthetic_contents('(a(b(c)(d)e)(f)g)'))
[(2, 'c'), (2, 'd'), (1, 'b(c)(d)e'), (1, 'f'), (0, 'a(b(c)(d)e)(f)g')]
3 голосов
/ 05 июня 2018

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

def push(obj, l, depth):
    while depth:
        l = l[-1]
        depth -= 1

    l.append(obj)

def parse_parentheses(s):
    groups = []
    depth = 0

    try:
        for char in s:
            if char == '(':
                push([], groups, depth)
                depth += 1
            elif char == ')':
                depth -= 1
            else:
                push(char, groups, depth)
    except IndexError:
        raise ValueError('Parentheses mismatch')

    if depth > 0:
        raise ValueError('Parentheses mismatch')
    else:
        return groups

print(parse_parentheses('a(b(cd)f)')) # ['a', ['b', ['c', 'd'], 'f']]
0 голосов
/ 26 ноября 2010 
#!/usr/bin/env python
import re

def ParseNestedParen(string, level):
    """
    Generate strings contained in nested (), indexing i = level
    """
    if len(re.findall("\(", string)) == len(re.findall("\)", string)):
        LeftRightIndex = [x for x in zip(
        [Left.start()+1 for Left in re.finditer('\(', string)], 
        reversed([Right.start() for Right in re.finditer('\)', string)]))]

    elif len(re.findall("\(", string)) > len(re.findall("\)", string)):
        return ParseNestedParen(string + ')', level)

    elif len(re.findall("\(", string)) < len(re.findall("\)", string)):
        return ParseNestedParen('(' + string, level)

    else:
        return 'fail'

    return [string[LeftRightIndex[level][0]:LeftRightIndex[level][1]]]

Тесты: 

if __name__ == '__main__':

    teststring = "outer(first(second(third)second)first)outer"

    print(ParseNestedParen(teststring, 0))
    print(ParseNestedParen(teststring, 1))
    print(ParseNestedParen(teststring, 2))

    teststring_2 = "outer(first(second(third)second)"

    print(ParseNestedParen(teststring_2, 0))
    print(ParseNestedParen(teststring_2, 1))
    print(ParseNestedParen(teststring_2, 2))

    teststring_3 = "second(third)second)first)outer"

    print(ParseNestedParen(teststring_3, 0))
    print(ParseNestedParen(teststring_3, 1))
    print(ParseNestedParen(teststring_3, 2))

выход: 

Running tool: python3.1

['first(second(third)second)first']
['second(third)second']
['third']
['first(second(third)second)']
['second(third)second']
['third']
['(second(third)second)first']
['second(third)second']
['third']
>>>
...