Контекст
Линтер конфигов первым делом смотрит, не забыл ли автор закрыть скобку. Открыли ( — где-то ниже должна быть парная ), причём вложенность обязана соблюдаться: [ нельзя закрыть через ). Считать скобки счётчиком недостаточно — в строке ([)] открывающих и закрывающих поровну, а конфиг всё равно битый. Спасает стек: каждую открывающую кладём на вершину, каждая закрывающая обязана снять именно парную ей.
Задача
Реализуйте функцию is_balanced(source): source — строка с текстом конфига. Верните True, если все скобки ()[]{} корректно вложены и закрыты, иначе False.
Правила
- Идите по строке слева направо.
- Открывающую скобку (
(,[,{) кладите на вершину стека. - Закрывающая (
),],}) должна снять с вершины парную ей открывающую. Если стек пуст или на вершине другая открывающая — вернитеFalse. - Любой символ, не являющийся одной из шести скобок, игнорируется.
- После обработки всей строки стек должен быть пуст — иначе осталась незакрытая скобка и ответ
False. - Пустая строка сбалансирована: верните
True.
Примеры
is_balanced("(a[b]{c})")
# True — каждая закрывающая снимает парную вершину, стек опустел
is_balanced("([)]")
# False — скобок поровну, но «)» приходит при вершине «[»
is_balanced("(()")
# False — одна «(» осталась незакрытой
is_balanced("")
# True — пустой ввод сбалансированГде это пригодится
Сопоставление скобок по стеку — основа любого парсера: компилятор, линтер, подсветка пар скобок в редакторе. Тот же приём проверяет парность тегов в HTML и вложенность блоков в JSON или YAML. Везде, где есть «открыли — закрыли» с вложенностью, под капотом работает стек.