CodinGame | Brackets, extreme edition | C++

Приветствую! Вы наверняка сталкивались со всякими разными контейнерами. Например с очередями и односвязными списками. В задаче, которую я разбираю в этой заметке, без использования #stack придётся изобретать велосипед.

Описание задачи: Вы должны определить, имеет ли строка допустимые скобки. Это означает, что все скобки (), квадратные скобки [] и фигурные скобки {} должны быть правильно спарены и вложены.

Входные данные:

Строка-выражение

Выходные данные:

true или false (string)

Пример:

Входные данные:

{([]){}()}

Выходные данные:

true

Brackets, extreme edition решение на C++:

Сначала кажется, что тут всё просто: нужно проверить пару условий, ввести какие-нибудь счётчики. Однако счётчики нужно ещё как-то грамотно обработать. А затем выползает ещё одна маленькая неприятность: нужно учитывать порядок вложенности. Эвристический подход нам не поможет. Для решения этой задачи создан контейнер <stack>. Принцип следующий: «последним вошёл — первым вышел» (last-in, first-out — LIFO).

Для перебора символов воспользуемся range-based циклом. Обязательно используем передачу по ссылке, чтобы не создавать копии объектов. Ссылка константная, потому что мы не планируем что-то менять. Алгоритм:

1. С помощью switch ищем открывающую скобку.

2. Если находим, добавляем в самый низ стека закрывающую.

3. В том случае, если мы наткнулись на закрывающую скобку, проверяем состояние стека.

4. Если он пустой или самый верхний элемент стека не совпадает с текущим, значит что-то не так с порядком вложенности скобок.

5. Если всё хорошо, удаляем верхний элемент стека, т.к. закрывающая скобка найдена и корректно обработана.

6. Проверяем состояние стека: если к концу обработки строки стек пуст, значит у каждой открывающей скобки есть закрывающая.

Итоговый код:

Послесловие:

Порешать задачи по программированию можно на CodinGame. -- © Bezukh Vladimir, 2019