Пишем свой алгоритм обработки
Разберём типичную задачу бэкенд-разработчика.
На сервер постоянно приходят разные запросы от других компьютеров. Прежде чем сервер ответит на запрос, он должен разобраться, правильно ли этот запрос составлен. В нашем случае запрос — это строка, внутри которой может быть несколько логических блоков, каждый из которых берётся в свои скобки: (), [] или {}.
Сложность в том, что такие блоки могут быть вложены друг в друга, например так: (.[.]){.}(.) или так: {([.].).}. При этом мы заранее не знаем количество скобок и уровни вложенности. Наша задача — проверить, правильно ли расставлены скобки. Это значит:
- открывающие скобки должны быть закрыты тем же видом скобок;
- все скобки должны быть закрыты в правильном порядке: последняя открывающая должна совпасть с первой закрывающей;
- у каждой открывающей скобки должна быть пара в виде закрывающей, и наоборот;
- кроме скобок в строке могут быть любые другие символы.
Например, () (.){} — это правильная последовательность скобок, (.){[].} — тоже правильная, а ({.)} — неправильная.
Нужно написать код, который берёт строку с запросом, проверяет её и сообщает, в порядке там скобки или нет.
Решение
Сразу сформируем строку, которую будем проверять. Писать будем на Python, но это можно сделать на любом другом языке:
# строка для проверки
input = '(Привет!)(Это){[журнал]}([]код)'
Теперь, чтобы было проще работать, избавимся от всех лишних символов в строке. Так как нам нужно сохранить оригинальный запрос, создадим новую переменную, пустую на старте, и заполним её только скобками. Для этого мы посмотрим все символы в исходной строке и возьмём оттуда только скобки:
А теперь — самая хитрость: в новой строке мы будем искать готовые пары скобок, которые стоят рядом, и убирать их. Логика такая: как бы мы ни вкладывали скобки друг в друга, всё равно в конце у нас будет одна открывающая, а за ней — такая же закрывающая. Так как мы убрали все лишние символы, то такие скобки будут идти сразу друг за другом: (), [] или {}. При этом, когда убираем внутренние скобки, внешние тоже начинают образовывать готовую пару. Сейчас покажем на примере.
В нашем случае строка без лишних символов будет выглядеть так: () (){[]}([]). Теперь уберём оттуда все готовые пары, шаг за шагом:
- ()(){[]}([]) → (){[]}([])
- (){[]}([]) → {[]}([])
- {[]}([]) → {}([])
- {}([]) → ([])
- ([]) → ()
- () → пустая строка
Получается, что если мы в итоге получим пустую строку, то все скобки были расставлены правильно. А если в новой строке останутся символы — значит, им не нашлось пары и скобки были расставлены неправильно.
Запишем это в коде:
Теперь попробуйте сделать это на JavaScript. Если это покажется слишком лёгкой задачей — сделайте так, чтобы код сообщал номер символа, где первый раз встречается неправильная скобка.