Тип 2
В прошлой статье мы познакомились с основными способами решения и типизацией 24 заданий ЕГЭ по информатике. Ко всему прочему, научились решать задания первого типа с помощью регулярных выражений.
В этой статье продолжим работать с регулярными выражениями ведь у нас на очереди второй тип, в котором предстоит работать с арифметическими выражениями.
Текстовый файл в заданиях второго типа состоит, обычно, из цифр и двух знаков арифметических операций. Следовательно, в нём среди обилия символов можно определить подстроки, которые будут корректными арифметическими выражениями. Например, такими будут следующие подстроки: «2+2», «12*2+3» и им подобные.
Ограничения здесь два: числа не могут иметь ведущие нули, и никакие два знака арифметических операций не должны стоять рядом. То есть такие подстроки уже не будут подходить под условие задания: «02+2», «1++2».
Что же до ответа, то зачастую требуется определить самую длинную подстроку, являющуюся корректным арифметическим выражением. Но есть и усложнения. Например, значение такого выражения должно равняться нулю или состоять это выражение может только из чётных чисел.
Алгоритм решения
Начнём с самой простой вариации этого задания:
«Текстовый файл состоит из цифр 0, 6, 7, 8, 9 и знаков арифметических операций «–» и «*» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами.
В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число 0 не имеет знака.»
При решении таких задач шаблоны регулярных выражений получаются довольно большими. Так что мы будем их разбивать на части и потом соединять все части вместе с помощью f-строк.
Для начала нам нужно определить шаблон для поиска числа. Число не должно начинаться с нуля, то есть используем такой диапазон: «[6789]». А после него может идти 0 и более всех доступных чисел: «[6789][06789]*». Но само число 0 тоже может встречаться в выражении, так что следует добавить и его в нашу запись: «0|[6789][06789]*». Соберём все в незахватывающую группу и передадим на хранение в переменную num:
Давайте проверим, что найдёт этот шаблон в такой строке: «-67*0—9-0*68-». Для этого воспользуемся такой программой:
В строке найдены все подходящие числа. Осталось теперь объединить их в корректные арифметические выражения. Здесь таких выражений два: «67 * 0» и «9 – 0 * 68».
Можно выявить такой шаблон: «Число (операция Число)*». То есть после найденного числа могут 0 и более раз повторяться группы, состоящие из знака арифметической операции и числа.
Запишем это отдельным шаблоном:
Обратите внимание, что мы подставляем в него уже известный нам шаблон определения числа — num.
Теперь найдём выражения в нашей тестовой строке:
Отлично, все работает, как мы и задумали. Добавляем блок кода с чтением файла:
Заменяем функцию на finditer():
И формируем ответ:
Запускаем программу и получаем число 154 — это и будем ответ на данное задание.
Пример 1
Рассмотрим еще одно похожее задание:
«Текстовый файл состоит из всех возможных шестнадцатеричных цифр и знаков «-» и «*» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами.
В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число 0 не имеет знака.»
Здесь все отличия будут в шаблоне для определения числа: теперь в нашем распоряжении не жалкие 5 цифр, а все цифры шестнадцатеричной системы счисления: от нуля до F.
В таком случае шаблон у нас будет выглядеть так: «(?:0|[1-9A-F][0-9A-F]*)». И это будет единственное изменение в предыдущем коде, если не считать имя файла:
Запускаем программу и видим число 768, которое и записываем в ответ.
Пример 2
На очереди такое задание:
«Текстовый файл состоит из десятичных цифр, знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами, кратными двум.
В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули.»
Здесь наложено ограничение на числа арифметического выражения: они должны быть кратным двум. Кратны двум любые числа, заканчивающиеся на чётную цифру (0, 2, 4, 6, 8). И сами эти цифры кратны двум, само собой.
Отметим это в нашем шаблоне: «(?:[1-9][0-9]*[02468]|[02468])». Обратите внимание, здесь сначала идёт описание всех «длинных чисел» и только потом ищутся сами чётные цифры! Только такой порядок приведёт к верному ответу.
Левая часть шаблона ищет число, начинающееся с любой цифры кроме нуля, в котором затем следует 0 и более любых цифр, а в конце обязательно стоят чётные цифры. Правая же часть ищет просто цифры 0, 2, 4, 6 и 8.
С шаблоном закончили, можно подставлять его в уже знакомый код:
После его запуска видим на экране ответ на это задание — 127.
Пример 4
Напоследок рассмотрим такое задание:
«Текстовый файл состоит из десятичных цифр, знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю.
В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули.»
Теперь от нас требуется найти не просто самое длинное корректное арифметическое выражение, но такое, значение которого будет равно 0.
Звучит, конечно, пугающе. Но на деле все сводится к одному простому действию. Давайте подумаем, когда значение выражения, в котором есть операции сложения и умножения целых неотрицательных чисел, будет равно нулю?
Когда в этом выражении есть умножение на ноль в каждом слагаемом! Например, вы можете записать очень длинное выражение:
1231423423 * 12312312312 + 8932972389462 * 235434534 = ?
Но стоит добавить всего два символа «* 0» к каждому слагаемому, и значение всего выражение будет приравнено к нулю:
1231423423 * 12312312312 * 0 + 8932972389462 * 235434534 * 0 = 0 + 0 = 0
Теперь продумаем алгоритм, как определять такие группы.
Начнём с конца. Нам нужны группы вида: «Произведение (+ Произведение)». Групп «(+ Произведение)» должно быть 0 и более. С этим шаблоном мы знакомы из предыдущих заданий.
Теперь копаем глубже. Каждое произведение должно равняться нулю. Следовательно, у нас должно быть что-то вроде этого: «(Число *) 0 (* Число)». Этих групп внутри скобок может быть 0 и более раз. То есть нам подходят как числа, умноженные на ноль, так и само число 0: «1 * 0», «1 * 0 * 2», «0 * 3», «4 * 0 * 5 * 6».
Последний уровень нашего погружения. Как же должно выглядеть число? Тут уже ничего сложного нет — это обычное десятичное число без ведущих нулей или само число 0. В этот раз ноль ставим в левой части выражения, перед знаком «|»!
Собираем все наши описанные шаблоны до кучи:
Теперь произведение:
Обратите внимание, что звёздочка перед нулём — это не умножение, а квантификатор! Он означает, что групп «(?:{num}\*)» должно быть 0 и более штук. Знаки умножения здесь экранированы — «\*».
И окончательный шаблон:
Подставляем в наш стандартный код:
Запускаем программу и получаем число 142, которое и запишем в ответ.
На этом мы закончим разбор алгоритма решения 24 заданий второго типа. Следующую статью посвятим уже третьему типу этих заданий и научимся работать с методом замены и разделения.