Проверить правильно ли вложены скобки 〈 ( { [ ] } ) 〉в тексте

#python #алгоритм #python_3x

Вот пример, где скобки 〈 п{р}авильно (вло[ж]ены)〉.
Вот пример, где скобки НЕ 〈 пр(авильно вложены〉).
    

Ответы

Ответ 1

Классическое решение с использованием стэка, который сохраняет
типы (несбалансированных) открывающих скобок:


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

Продолжать до конца текста и если стэк пустой, то текст содержит
только правильно вложенные скобки.


На Питоне 3:

def is_balanced(text, brackets="〈〉()[]{}"):
    opening, closing = brackets[::2], brackets[1::2]
    stack = [] # keep track of opening brackets types
    for character in text:
        if character in opening: # bracket
            stack.append(opening.index(character))
        elif character in closing: # bracket
            if stack and stack[-1] == closing.index(character):
                stack.pop()  # remove the matched pair
            else:
                return False # unbalanced (no corresponding opening bracket) or
                             # unmatched (different type) closing bracket
    return (not stack) # no unbalanced brackets


В этом случае тип скобки (фигурная/квадратная/итд) представлен индексом в opening
списке, содержащим все открывающие скобки. closing содержит закрывающие скобки тех
же типов на тех же индексах.

Пример:

>>> is_balanced('скобки 〈 п{р}авильно (вло[ж]ены)〉')
True
>>> is_balanced('скобки НЕ 〈 пр(авильно вложены〉)')
False


Ответ 2

Можно удалять плоские (невложенные) сбалансированные части пока это возможно, а затем
проверить остались ли [несбалансированные] скобки в тексте:

def is_balanced(text, brackets="〈〉()[]{}"):
    L = list(map(re.escape, brackets))  # make it safe for a regex
    regex = re.compile('|'.join(  # O <-> opening, C <-> closing
        ['{O}[^{B}]*{C}'.format(B=''.join(L),**vars()) for O, C in zip(L[::2], L[1::2])]))
    n = "number of substitutions"
    while n:
        text, n = regex.subn('', text)  # remove non-nested/flat balanced parts
    return set(brackets).isdisjoint(text)  # no [unbalanced] brackets left