Страницы

Поиск по вопросам

среда, 31 октября 2018 г.

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

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


Ответ

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

Комментариев нет:

Отправить комментарий