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

Еще одна очень часто встречающаяся задача на собеседовании. Относится к алгоритмическим, решение должно укладываться по сложности в O(n).

Условие:

Дана строка содержащая скобки разных видов: '(, ), {, }, [, ]'. Необходимо определить является ли скобочная последовательность правильной, а именно:

• для каждой открывающей скобки есть закрывающая из той же пары, например, для открывающей '[' будет ']'
• скобки закрываются в правильном порядке, то есть не может быть так, что сначала идет закрывающая, а потом открывающая из той же пары
• пустая строка считается правильной
• в строке кроме скобок больше ничего не содержится. это условие может не соблюдаться, если на собесе захотят усложнить задачу

Начнем с тестовых кейсов, чтобы лучше понять условие:

1. '' —> true (пустая строка)
2. () —> true
3. ()[]{} —> true
4. ({}) —> true
5. ][ —> false
6. (} —> false
7. {}) —> false

Как будем решать:

Вспоминаем такую структуру данных как стек, которая основывается на последовательности LIFO (Last In First Out).

• В цикле, если нам встречается открывающаяся скобка, то кладем ее на стек.
• Если встречается закрывающаяся скобка, то сравниваем ее с последним элементом в стеке, если скобки матчатся друг с другом (открывающая из стека равна соответствующей закрывающей), то вынимаем открывающую скобку из стека.
• Если скобки не совпадают, сразу возвращаем false из функции — последовательность неправильная.
• После завершения цикла проверяем, что стек пустой и все скобки совпали попарно. Если не пустой возвращаем false.

Реализация на Go

1. В начале функции инициализируем мапу с парами скобок
2. Далее создаем стек на основе слайса
3. (Опционально) Проверяем, что в строке есть хотя бы две скобки
4. Далее, в цикле реализован рассмотренный выше алгоритм

Код можно скопировать здесь

Реализация на Python

В питоне выглядит лаконичнее за счет наличия метода извлечения элемента из списка.