Вот пример, где скобки 〈 п{р}авильно (вло[ж]ены)〉. Вот пример, где скобки НЕ 〈 пр(авильно вложены〉).
Ответ
Классическое решение с использованием стэка, который сохраняет
типы (несбалансированных) открывающих скобок:
Для каждого символа в тексте
проверить является ли он открывающей скобкой
если является, то добавить в стэк тип этой скобки (угловая/круглая/итд)
если нет, то проверить является ли символ закрывающей скобкой
если является и последняя добавленная открывающая скобка совпадает,
то убрать её из стэка (найдена совпавшая пара скобок)
иначе завершить алгоритм—найдена неправильно вложенная скобка.
Продолжать до конца текста и если стэк пустой, то текст содержит
только правильно вложенные скобки.
На Питоне 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
Комментариев нет:
Отправить комментарий