Навигация по странице
Тип 2
Ко второму типу мы отнесём те задания, в формулировках которых вы можете встретить фразу «корректное арифметическое выражение с целыми неотрицательными числами».
Какое арифметическое выражение мы можем назвать корректным? Это выражение вида «<цифра><знак арифметической операции><цифра>».
Например, всем до боли знакомое выражение «2+2» – является корректным. А вот выражения «2–2», «02+2», «+2+2» уже не будут корректными.
Перейдём к формулировке задания.
Задание 2402
«Текстовый файл состоит из цифр 0, 7, 8, 9 и знаков арифметических операций «-» и «*» (вычитание и умножение).
Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число 0 не имеет знака.
В ответе укажите количество символов»
До сих пор наши регулярные выражения были простые и легко читались. Но порой строка с регулярным выражением может содержать слишком много групп, диапазонов и так далее. В таких случаях лучше разбивать её на несколько и выносить логические группы в отдельные переменные.
Здесь можно вынести группу, которая обозначает число, состоящее из цифр 0, 7, 8 и 9. Такое число не должно начинаться с нуля и может содержать в себе одну и более цифр.
Следовательно, первую цифру (или единственную) этого числа можем определить таким диапазоном [789]. Тогда все остальные числа должны принадлежать диапазону [0789], и их может быть 0 и более (квантификатор «*»). Но также необходимо учесть, что это число может быть просто нулём.
Запишем это выражение в переменную num:
num = r'(?:[789][0789]*|0)'
Для группировки частей регулярного выражения мы используем синтаксис групп без захвата содержимого «(?:…)».
Теперь нам надо сформировать само регулярное выражение, которое будет искать нужную подстроку в тексте. Его можно определить так:
- Любое число (0, 70, 78 и т.д.): переменная num
- Знак «-» или «*»: символ из диапазона [-*]
- Любое число (0, 70, 78 и т.д.): переменная num
Причём символы из 2 и 3 пунктов мы можем определить в единую группу, которая может повторяться 1 и более раз (квантификатор «+»): «([-*]{num })+».
В такой записи мы будем использовать синтаксис f-строк, чтобы подставлять уже готовые выражения из других переменных в наше итоговое регулярное выражение.
pattern = rf'{num}([-*]{num})+'
Давайте проверим наше регулярное выражение на такой строке: «7-70*9–708*807-7**». Здесь у нас есть два корректных арифметических выражений: «7-70*9» (длина 6 символов) и «708*807-7» (длина 9 символов).
Воспользуемся такой программой для проверки:
import re
data = '7-70*9--708*807-7**'
num = r'(?:[789][0789]*|0)'
pattern = rf'{num}([-*]{num})+'
matches = re.finditer(pattern, data)
for match in matches:
print(f"Подстрока: {match.group()}")
print(f"Длина: {len(match.group())}")
>>>Подстрока: 7-70*9
>>>Длина: 6
>>>Подстрока: 708*807-7
>>>Длина: 9
Все получилось, как мы и ожидали. Значит, добавляем в наш код блоки с чтением данных из файла и подсчётом максимальной длины подстроки:
import re
with open('2402.txt', 'r') as file:
data = file.readline()
num = r'(?:[789][0789]*|0)'
pattern = rf'{num}([-*]{num})+'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer)
В результате получаем число 111, которое и будет ответом на данное задание.
Пример 1
Давайте теперь рассмотрим более сложную формулировку задания 24 второго типа.
Задание 2418
«Текстовый файл состоит из десятичных цифр, знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами, кратными двум. В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули.
В ответе укажите количество символов»
Регулярное выражение для этого задания будет не сильно отличаться от прошлого. Ключевое отличие будем в том, что нужно находить только те числа, которые будут кратны двум. Давайте вспомним признаки делимости числа на 2.
Число делится на 2 только в том случае, если его последняя цифра чётная. То есть, если число состоит из более двух цифр, будем требовать, чтобы последняя была 0, 2, 4, 6 или 8. В противном случае, если число однозначное, то нам будут подходить только числа 0, 2, 4, 6 или 8.
Используя эту информацию, напишем регулярное выражение:
num = r'(?:[1-9][0-9]*[02468]|0|2|4|6|8)'
Осталось только подставить выражение в разобранный ранее код.
import re
with open('2418.txt', 'r') as file:
data = file.readline()
num = r'(?:[1-9][0-9]*[02468]|0|2|4|6|8)'
pattern = rf'{num}(?:[+*]{num})+'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer)
В итоге видим на экране ответ на данное задание – 127.
Пример 2
Далее рассмотрим самое сложное 24 задание этого типа, которое было представлено в основной волне ЕГЭ 2024 года.
Задание 2415
«Текстовый файл состоит из десятичных цифр, знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю. В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули.
В ответе укажите количество символов»
Вся его сложность заключается во фразе «значение которого равно нулю». То есть нам нужно найти самую длинную подстроку, среди тех, чьё значение равно 0.
Здесь нам повезло в том, что есть только операции суммирования и умножения. Сразу можно догадаться, что выражение может быть равно нулю, только тогда, когда этим выражением является умножение любого числа на 0.
Тогда наша задача будет найти сначала подстроку, в которой есть хотя бы одно умножение на 0, а затем найти группу таких подстрок, объединённых символом «+».
Начнем с обозначения числа, состоящего из одной и более цифры:
num = r'(?:[0-9]+)'
Под такую запись подходят как число «012», так и число «120». Но здесь мы вольны включить 0 в диапазон ввиду того, что все числа в файле не содержат незначащих нулей.
Теперь напишем регулярное выражение, которое определяет строку с умножением на какое-либо число, подходящее под шаблон в num (по факту – любое).
x_num = rf'(?:\*{num})'
Такое выражение будет находить следующие подстроки: «*0», «*1», «*123» и так далее.
И переходим к самому массивному выражению в этом задании. Здесь нужно определить шаблоны для поиска всех произведений: «ноль * число * число…» и «число * число… * ноль * число…» (многоточием здесь определяется последовательность из умножений на число).
Написать выражение для первого варианта «ноль * число * число…» довольно просто. У нас есть выражение в x_num, определяющее умножение, так что просто добавим 0 слева: «0{x_num}*».
Теперь вторая часть, когда умножение на 0 может быть где-то между произведением других чисел. Сначала напишем выражение для произведения чисел до 0: «{num}{x_num}*?».
Обратите внимание, что тут используется ленивый квантификатор «*», который ищет минимально возможное совпадение. Работу ленивых квантификаторов мы разбирали в прошлой статье.
Добавляем умножение на 0: «{num}{x_num}*?\*0» (здесь не забываем про экранирование знака умножения). После чего дописываем еще одно и более умножений на любое число: «{num}{x_num}*?\*0{x_num}*».
В итоге получаем вот такое большое регулярное выражение:
mult = rf'(?:0{x_num}*|{num}{x_num}*?\*0{x_num}*)'
Давайте уже на этом этапе проверим наше регулярное выражение. На вход нашей программы подадим строку «0*1++1*0*2*2++1*2». Здесь у нас только два арифметических выражения, содержащих умножение на 0:
- 0*1 (подходит под первый вариант «0{x_num}*»)
- 1*0*2*2 (подходит под второй вариант «{num}{x_num}*?\*0{x_num}*»)
Воспользуемся такой программой для проверки:
import re
data = '0*1++1*0*2*2++1*2'
num = r'(?:[0-9]+)'
x_num = rf'(?:\*{num})'
mult = rf'(?:0{x_num}*|{num}{x_num}*?\*0{x_num}*)'
matches = re.finditer(mult, data)
for match in matches:
print(f"Подстрока:{match.group()}")
print(f"Длина:{len(match.group())}")
>>>Подстрока:0*1
>>>Длина:3
>>>Подстрока:1*0*2*2
>>>Длина:7
Как видим, программа отработала корректно. Значит, можем смело создавать наши регулярные выражения дальше.
Теперь нам нужно собрать вместе несколько групп mult, объединённых знаком «+». Запишем это следующим образом:
pattern = rf'{mult}(?:\+{mult})*'
И снова проверим корректность выражения на простеньком примере. Пусть теперь проверяться будет такая строка: «1*2+1*0+1*0*2*2+1*2». Здесь должна вернуться одна подстрока, в которой произведения «1*0» и «1*0*2*2» объединены плюсом.
Напишем программу для проверки:
import re
data = '1*2+1*0+1*0*2*2+1*2'
num = r'(?:[0-9]+)'
x_num = rf'(?:\*{num})'
mult = rf'(?:0{x_num}*|{num}{x_num}*?\*0{x_num}*)'
pattern = rf'{mult}(?:\+{mult})*'
matches = re.finditer(pattern, data)
for match in matches:
print(f"Подстрока:{match.group()}")
print(f"Длина:{len(match.group())}")
>>>Подстрока:1*0+1*0*2*2
>>>Длина:11
Регулярное выражение составлено верно, теперь дописываем код и ожидаем получить ответ на это задание:
import re
with open('2415.txt', 'r') as file:
data = file.readline()
num = r'(?:[0-9]+)'
x_num = rf'(?:\*{num})'
mult = rf'(?:0{x_num}*|{num}{x_num}*?\*0{x_num}*)'
pattern = rf'{mult}(?:\+{mult})*'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer)
В результате получаем число 142.