Несложная классическая задача на структуры данных, которая усложнена форматом входных данных. Читаем условие:
Итак, первая сложность в этой задаче - как считать данные? Действительно, нет классического N - количества строк. А это значит, что надо считывать все строки до конца.
Построчное считывание в Python можно организовать через следующую конструкцию:
Такой цикл считает весь входной файл и сам разделит его на строки. Единственная особенность - в строках l будут находиться и символы переноса строки, поэтому при их обходе надо делать l.strip() (см. строку 7).
Теперь задачу можно переформулировать: дана строка, надо проверить баланс скобок, то есть правильную вложенность их друг в друга.
Проверить правильную вложенность скобок можно вычёркиванием рядом стоящих открывающих и закрывающих скобок одного типа, то есть подстрок вида "()", "[]", "{}". И повторением этого процесса, пока возможно. Если в результате получится пустая строка, то скобочная последовательность была правильной.
При таких небольших ограничениях на входные данные, как в данной задаче, можно реализовать процесс итеративного вычёркивания. Но не будем. А воспользуемся структурой данных стек.
Стек — структура данных, представляющая собой список элементов, организованных по принципу LIFO (last in — first out, «последним пришёл — первым вышел»).
Чаще всего принцип работы стека сравнивают со стопкой тарелок. Можно класть только наверх стопки или брать сверху. Чтобы взять вторую сверху, нужно сначала снять верхнюю.
В Python стек можно реализовать на списке, используя методы append и pop, предполагая, что верх стопки - последний элемент списка. Тогда все операции со стеком будут выполняться за O(1).
Для решения задачи в стеке будем хранить ещё не вычеркнутые открывающие скобки в порядке их следования в строке. Тогда:
- если следующий элемент - открывающая скобка, то надо её добавить в стек,
- если - закрывающая, то надо проверить, что она соответствует последней незачёркнутой открывающей скобке (то есть последней скобке в стеке). В случае соответствия, надо обе эти скобки вычеркнуть (то есть удалить элемент из стека).
Не забываем в самом конце проверить, что в стеке ничего не осталось.
Здесь мы для упрощения условия и повышения наглядности и масштабируемости решения (см. строку 10), используем словарь с парными элементами:
Таким образом мы получили решение за один проход по строке и познакомились со структурой данных стек. А также узнали, как считывать все данные из файла.
Предыдущий выпуск: Задача 431. Путь коня
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.