Последовательность скобок
Вы пишите текстовый редактор с крутой подсветкой синтаксиса. Вы хотите исправлять ошибки программиста, в том числе неправильно расставленные скобки.
Напишите функцию, которая будет исправлять последовательность скобок, используя минимальное количество изменений. Возможные скобки []
, ()
, {}
, <>
. Интуитивно понятно, что такое правильная последовательность, однако более формальное определение, а так же основные методы работы с ними можно найти тут.
Метод должен принимать строку, состоящую только из разрешенных скобок, и возвращать строку той же длины, содержащую правильную последовательность скобок. Изменений нужно сделать как можно меньше.
Изменять можно только закрывающие скобки, т.е. ]})>
. Открывающие скобки должны остататься без изменений. Если исправить строку невозможно, верните null
.
Примеры
Решение
Попробуем сделать так - сначала определить, можем ли мы вообще получить корректную последовательность, и если да, то уже составить ее. Как это определить? Попробуем просто посчитать количество открывающих и закрывающих скобок, и если они равны - значит последовательность составить можно.
Однако легко придумать строку, которая будет ложно распознана как верная, например ][
. Обратившись к формальному определению, можно заметить ...любой префикс которой содержит количество открывающих скобок, больше или равное закрывающим...
. Под префиксом здесь имеется ввиду любая подстрока, начало которой совпадает с началом любой строки (обратное префиксу - суфикс: любая подстрока, конец которой совпадает с концом исходной строки). Таким образом, в наш код нужно добавить такую проверку.
Теперь напишем код для составления самой последовательности. Воспользуемся структурой данных стек - одну из самых важных структур в работе со строками и теории формальных языков в общем. Будем формировать правильную строку с нуля. Если встретим открывающую скобку - положим ее наверх стека и добавим к возвращаемой строке. Если закрывающую - посмотрим, какая была последняя “неудовлетворенная” открывающая скобка, и поставим нужную скобку. Например, в строке “([].” на месте точки последняя “неудовлетворенная” скобка это “(“.
Все хорошо, и работает. Однако код получился громоздким, и создается ощущение, что мы делаем много лишних движений. Попробуем избавиться от проверки строки на правильность, и сразу формировать строку, по ходу дела понимая, если составить правильную последовательность скобок не получится. Что будет, если в строке let br = stack.pop();
стек окажется пустым? Это означает, что мы уже “удовлетворили” все открывающие скобки, и при этом встретили еще одну закрывающую скобку. Например, если на месте точки “[[]].” стоит закрывающая скобка - такая строка некорректна. Также, что произойдет для строки “[[[”? После формирования, на стеке все еще будут “неудовлетворенные” открывающие скобки. Такая строка тоже некорректна.
Из хороших решений стоит отметить решение Евгения Зайцева.
Комментарии