Как компьютер находит неправильные скобки и кавычки — Журнал «Код» программирование без снобизма

Разберём типичную задачу бэкенд-разработчика.

На сервер постоянно приходят разные запросы от других компьютеров. Прежде чем сервер ответит на запрос, он должен разобраться, правильно ли этот запрос составлен. В нашем случае запрос — это строка, внутри которой может быть несколько логических блоков, каждый из которых берётся в свои скобки: (), [] или {}.

Сложность в том, что такие блоки могут быть вложены друг в друга, например так: (..[..]){..}(..) или так: {([..]..)..}. При этом мы заранее не знаем количество скобок и уровни вложенности. Наша задача — проверить, правильно ли расставлены скобки. Это значит:

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

Например, ()(..){} — это правильная последовательность скобок, (..){[]..} — тоже правильная, а ({..)} — неправильная.

Нужно написать код, который берёт строку с запросом, проверяет её и сообщает, в порядке там скобки или нет.

Сразу сформируем строку, которую будем проверять. Писать будем на Python, но это можно сделать на любом другом языке:

# строка для проверки input = '(Привет!)(Это){[журнал]}([]код)'

Теперь, чтобы было проще работать, избавимся от всех лишних символов в строке. Так как нам нужно сохранить оригинальный запрос, создадим новую переменную, пустую на старте, и заполним её только скобками. Для этого мы посмотрим все символы в исходной строке и возьмём оттуда только скобки:

# строка, с которой в итоге будем работать, на старте пустая
s = ''
# список скобок
brackets = '()[]{}'
# перебираем все символы в исходной строке
for x in input:
	# если очередной символ — скобка
	if x in brackets:
		# добавляем его в новую строку
		s += x

А теперь — самая хитрость: в новой строке мы будем искать готовые пары скобок, которые стоят рядом, и убирать их. Логика такая: как бы мы ни вкладывали скобки друг в друга, всё равно в конце у нас будет одна открывающая, а за ней — такая же закрывающая. Так как мы убрали все лишние символы, то такие скобки будут идти сразу друг за другом: (), [] или {}. При этом, когда убираем внутренние скобки, внешние тоже начинают образовывать готовую пару. Сейчас покажем на примере.

В нашем случае строка без лишних символов будет выглядеть так: ()(){[]}([]). Теперь уберём оттуда все готовые пары, шаг за шагом:

()(){[]}([]) → (){[]}([])
(){[]}([]) → {[]}([])
{[]}([]) → {}([])
{}([]) → ([])
([]) → ()
() → пустая строка

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

Запишем это в коде:

# пока в новой строке есть пары скобок
while '()' in s or '[]'in s or '{}' in s:
	# меняем их на пустые символы → убираем пары скобок из строки
	s = s.replace('()','').replace('[]','').replace('{}','')
# если после обработки в новой строке остались символы — значит, было что-то непарное
if len(s) !=0:
	print('В скобках ошибка') 
# в противном случае, если строка пустая — значит, мы всё обработали верно
else:
	print('Всё в порядке')

Теперь попробуйте сделать это на JavaScript. Если это покажется слишком лёгкой задачей — сделайте так, чтобы код сообщал номер символа, где первый раз встречается неправильная скобка.

# стока для проверки
input = '(Привет!)(Это){[журнал]}([]код)'

# строка, с которой в итоге будем работать, на старте пустая
s = ''
# список скобок
brackets = '()[]{}'
# перебираем все символы в исходной строке
for x in input:
	# если очередной символ — скобка
	if x in brackets:
		# добавляем его в новую строку
		s += x
# пока в новой строке есть пары скобок
while '()' in s or '[]'in s or '{}' in s:
	# меняем их на пустые символы → убираем пары скобок из строки
	s = s.replace('()','').replace('[]','').replace('{}','')
# если после обработки в новой строке остались символы — значит, было что-то непарное
if len(s) !=0:
	print('В скобках ошибка') 
# в противном случае, если строка пустая — значит, мы всё обработали верно
else:
	print('Всё в порядке')

Апскиллинг, как говорится

Апскиллинг — это, например, переход с уровня junior на уровень middle, а потом — senior. У «Яндекс Практикума» есть курсы ровно для этого: от алгоритмов и типов данных до модных фреймворков.