Правильная скобочная последовательность

Дана строка состоящая из следующего набора скобок: (, ), {, }, [ и ]. Каждой открывающей скобке соответствует закрывающая, образуя пары.

Будем считать строку «правильной» если все скобки закрываются в нужном порядке, т.е:

• для каждой открывающей есть закрывающая из той же пары;
• скобки закрываются в правильном порядке.

Пустая строка считается правильной.

Решение

Сперва важно понять, что означает «скобки закрываются в правильном порядке». Здесь очень важно привести несколько примеров, спросив себя (или интервьюера) «что должен выдать такой тест?». Различные тесты должны помочь понять этот самый «правильный порядок» и идею алгоритма.

Итак, тесты:

// true
isValid('()[]{}')
// true
isValid('{[]}')
// true
isValid('((()(())))')
// false
isValid('(]')
// false
isValid('([)]')

Глядя только на первые два примера легко выбрать неверную стратегию — посчитаем количество различных скобок и убедимся, что все образуют пары и лишних нет.

Однако, глядя на последний пример, становится ясно, что эта стратегия ошибочная. Действительно, есть две пары () и [], но скобки закрываются в неправильном порядке. Так что же такое правильный порядок?

На схеме одним цветом выделены правильные последовательности. Можно заметить рекурсивную природу задачи. Базовый случай — последовательность из двух скобок; задача — «вырезать» все базовые последовательности, т.е. скобки непосредственно рядом друг с другом, пока строка не опустеет, а если этого сделать не получается — последовательность не правильная.

Опишем алгоритм, пробегаемся по строке слева направо одним указателем:

• если встречается открывающая скобка — кладём на стек (как бы рекурсивно проваливаемся в проверку вложенной последовательности);
• если встречается закрывающая скобка, смотрим соответствует ли она последней открывающей (вершина стека), если да — снимаем со стека («вырезаем» базовую) и продолжаем;

После проверяем пустой ли стек: если да — все открывающие нашли свои закрывающие скобки в правильном порядке, т.е. последовательность валидная;

<aside> 💡 Стек в данном контексте — структура данных. По определению, такая структура, что за O(1) можно положить (push), снять (pop) и проверить (top) последний добавленный элемент.

</aside>