Ах, эти загадочные задания ЕГЭ по информатике!
Если раньше вы думали, что регулярные выражения — это какой-то секретный язык инопланетян, то после наших приключений с ними вы почувствуете себя почти программистом-экзорцистом. В прошлой статье мы уже познакомились с основами решения и типизацией 24 заданий ЕГЭ и даже научились ловко использовать регулярки для первого типа задач. Теперь же настало время перейти к более хитрому зверю — второму типу заданий, где нам предстоит разбираться с арифметическими выражениями.
Представьте себе текстовый файл — ну, знаете, такой же загадочный и таинственный, как дневник школьника, полный цифр и знаков арифметических операций. В этом файле можно найти подстроки, которые выглядят как корректные арифметические выражения.
Например: «2+2», «12*2+3» — простые вещи вроде того, как посчитать сдачу в магазине или сколько конфет у вас осталось после визита младшего брата. Но у нас есть два строгих правила: числа не могут начинаться с нуля (ведущие нули — это как носить шляпу задом наперед, просто не принято), а знаки операций не должны стоять рядом (то есть «1++2» — это уже не арифметика, а какая-то магия).
Задача часто сводится к тому, чтобы найти самую длинную такую подстроку — самый длинный кусочек текста из файла, который превращается в правильное арифметическое выражение.
Иногда добавляют дополнительные условия: например, чтобы значение этого выражения было равно нулю или чтобы все числа были чётными. Тут уж без калькулятора не обойтись!
Начнем с самой простой вариации — задания 2406. Представьте себе файл из цифр 0, 6, 7, 8 и 9 и знаков «–» и «*».
Наша цель — найти самую длинную последовательность символов без ведущих нулей и двойных операторов подряд. Кажется простым? А вот попробуйте объяснить это своей бабушке!
Она скажет: «Внучек мой дорогой, зачем тебе эти сложные задачи? Просто возьми калькулятор!» Но мы-то знаем: регулярные выражения помогут нам сделать это автоматом.
Для начала нужно составить шаблон для числа. Число не должно начинаться с нуля (ну разве что само число — ноль).
Значит берем цифры от 6 до 9 в качестве первой цифры и потом любые из набора {0,6,7,8,9} сколько угодно раз. Добавим ещё вариант для самого нуля — получается что-то вроде «0|[6789][06789]*». Это напоминает мне анекдот про программиста: «Почему программисты путают Хэллоуин и Рождество?
Потому что OCT 31 = DEC 25.» Вот так и у нас тут игра со значениями чисел!
Проверяем наш шаблон на строке типа «-67*0—9-0*68-» — находим все подходящие числа: «67», «0», «9», «0», «68». Далее объединяем их в корректные выражения по правилу: число за которым может идти операция плюс число опять и опять… Получаем две цепочки: «67*0» и «9–0*68».
Всё работает как часы!
Дальше читаем файл целиком (не забудьте про функцию finditer(), она как детектив ищет каждое совпадение!), считаем длины таких корректных последовательностей и выбираем максимальную. Запускаем программу — получаем число 154! Можно поздравить себя с победой над демоном регулярных выражений.