Выражения с условиями и баланс

Это дополнительный урок: такие условия есть в сборниках и пробниках, а задачи основных подтем решаются без него. Нужно самое длинное корректное выражение с + и *, значение которого равно нулю. Неужели придётся вычислять все выражения?

Нет. Сумма неотрицательных чисел равна нулю, только если каждое слагаемое — ноль. А произведение равно нулю, когда среди множителей есть 0. Значит, выражение — сумма произведений, и в каждом произведении есть число 0. Это снова шаблон: слагаемое — множители через *, среди которых 0.

import re s = '12*0+5*0*7+3'number = r'(?:0|[1-9][0-9]*)'term = r'(?:' + number + r'\*)*0(?:\*' + number + r')*'pattern = term + r'(?:\+' + term + r')*'for m in re.finditer(pattern, s):    print(m.group())

12*0 и 5*0*7 равны нулю, а слагаемое 3 — нет, на нём выражение обрывается. Внутри шаблона * пишут как \*: без обратной косой черты звёздочка значит «сколько угодно раз».

Нужно самое длинное корректное выражение, в котором не больше двух чисел. Почему нельзя просто поменять * в шаблоне на «не больше одного повтора»?

Потому что finditer отдаст непересекающиеся куски и может разрезать выражение неудачно. Надёжнее найти длинные выражения целиком, а внутри каждого перебрать окна из K соседних чисел. В строке 1+2+345678 при поиске сразу по два числа найдётся 1+2, а за ним 345678 — и лучший кусок 2+345678 потеряется.

import re s = '1+2+345678'K = 2best = 0for e in re.finditer(r'[1-9]+(?:[+*][1-9]+)*', s):    numbers = list(re.finditer(r'[1-9]+', e.group()))    for j in range(len(numbers)):        i = max(0, j - K + 1)        best = max(best, numbers[j].end() - numbers[i].start()) print(best)

numbers[j].start() и numbers[j].end() — где число начинается и где кончается внутри выражения. Окно из чисел с i по j — это кусок от начала i-го числа до конца j-го. Обрезать крайние числа невыгодно: длина уменьшится, а чисел меньше не станет.

Нужно выражение, в котором действия слева направо дают тот же порядок, что и правила математики. Когда это так?

Когда после первого + или − умножения уже нет. 2*3+4 считается слева направо правильно, а в 2+3*4 умножение надо сделать раньше сложения. Идём по найденному выражению и помним последний + или −. Встретили * после него — начало куска переносим за этот знак.

import re s = '6*2-3*4-5'number = r'(?:0|[1-9][0-9]*)'pattern = number + r'(?:[-+*]' + number + r')*'best = 0for match in re.finditer(pattern, s):    text = match.group()    start = 0    last = -1    for i in range(len(text)):        if text[i] in '+-':            last = i        elif text[i] == '*' and last >= start:            start = last + 1        best = max(best, i - start + 1) print(best)

Подходят 6*2-3 и 3*4-5, по 5 символов. Всё выражение — нет: умножение 3*4 стоит после вычитания.

Нужно наибольшее значение суммы натуральных чисел со знаками + и −, которая стоит сразу после буквы C. Самая длинная сумма — самая большая?

Нет: вычитание её уменьшает. Поэтому перебирают начальные части суммы, которые кончаются целым числом, и считают значение каждой. Обрывать число посередине невыгодно: после + целое число больше своего начала, а перед − выгоднее остановиться вовсе.

import re s = 'C12+5-30+7D3+4'best = Nonefor match in re.finditer(r'C([1-9]+(?:[-+][1-9]+)*)', s):    total = 0    for term in re.finditer(r'([-+]?)([1-9]+)', match.group(1)):        value = int(term.group(2))        if term.group(1) == '-':            total -= value        else:            total += value        if best is None or total > best:            best = total print(best)

Круглые скобки в шаблоне запоминают части совпадения: match.group(1) — сама сумма без буквы C, term.group(1) — знак, term.group(2) — число. Начальные части 12, 12+5, 12+5-30, 12+5-30+7 дают 12, 17, −13 и −6; наибольшее — 17. Сумма 3+4 стоит после D и не считается.

Нужен самый длинный фрагмент, в котором букв ровно вдвое больше, чем цифр. Окно здесь не работает: условие то выполняется, то нет, и непонятно, когда сдвигать левую границу. Что делать?

Считать баланс: за букву +1, за цифру −2. Во фрагменте букв вдвое больше цифр, когда его баланс равен нулю — то есть когда на его границах накопленный баланс одинаковый. Для каждого значения баланса запоминаем, где оно встретилось впервые: от первого появления до текущего символа — самый длинный подходящий фрагмент с таким концом.

Запусти по шагам строку MKL1N и следи за словарём first. first = {0: -1} значит: до начала строки, на условной позиции −1, баланс был нулевым.

s = 'MKL1N'balance = 0first = {0: -1}best = 0for i in range(len(s)):    balance += -2 if s[i].isdigit() else 1    if balance in first:        best = max(best, i - first[balance])    else:        first[balance] = i print(best)

После M баланс 1, на позиции 3 — снова 1: между ними фрагмент KL1, две буквы и одна цифра. Ответ — 3. Если в строке есть символы, которые не буквы и не цифры, сначала реши по условию, дают ли они 0 или обрывают фрагмент.

• Значение 0каждое слагаемое — произведение с нулём
• Не более K чиселсначала целые выражения, потом окна из K чисел
• Порядок действийпосле + или − умножения нет
• Сумма после буквыперебор начальных частей до целого числа
• Балансодинаковый на границах — словарь первых появлений