24. Подсчет символов: Текстовый файл состоит из цифр 0, 2, 3, 4, 5 и знаков арифметических операций…
Текстовый файл состоит из цифр $0$, $2$, $3$, $4$, $5$ и знаков арифметических операций «$-$» и «$*$» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число $0$ не имеет знака.
В ответе укажите количество символов.
Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $2$–$5$, за которой идут любые цифры набора $0$, $2$, $3$, $4$, $5$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.
Этот файл устроен иначе, чем предыдущие. Здесь очень много нулей и знаков операций, а длинных блоков цифр почти нет. Найденный фрагмент состоит в основном из цепочек вида $00-00$, где каждое число — одиночный ноль. Это законно: $0$ сам по себе корректное число без ведущих нулей. А вот кусок $00$ уже недопустим, и именно на таких местах цепочки рвутся.
Отсюда видно, зачем в разборе нужна отдельная ветка j == r. Если блок цифр начинается с нуля и состоит из одного символа, это число $0$, и оно начинается с начала блока, значит к нему можно приклеить выражение слева. Если же блок начинается с нуля и тянется дальше, стартовать приходится с первой ненулевой цифры, а такой обрезанный старт влево уже не продолжить — слева стоит цифра.
Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, кончавшееся на два символа левее начала числа.
s = open('24-18.txt').read().strip()
n = len(s)
ops = set('-*')
L = [0] * n # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0 # начало текущего блока цифр
for j in range(n):
if s[j] in ops:
r = j + 1
continue
# 1) выражение из одного числа
if s[r] != '0': # блок начинается со значащей цифры
cur = j - r + 1
chain = r
elif j == r: # само число 0
cur = 1
chain = r
else: # блок начался с 0 — стартуем с первой ненулевой
q = r
while q <= j and s[q] == '0':
q += 1
cur = j - q + 1 if q <= j else 1
chain = -1 # слева цифра, знак операции не приписать
# 2) приклеиваем слева выражение через знак операции
if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
cur = max(cur, L[chain-2] + 1 + (j - chain + 1))
L[j] = cur
best = max(best, cur)
print(best) # 193
Проверка найденного фрагмента: длина $193$, он начинается с $0-0204024-0000*$ и кончается на $0-0-0-0-000$, целиком распознаётся регулярным выражением для корректной записи. Слева от него $-0*-$, то есть перед стартом знак, а перед ним ещё один — влево не растянуть. Справа идёт $*-$, два знака подряд, что запрещено.