Обработка символьных строк

В заданиях этого урока в файле находится длинная строка: набор букв, цифр и знаков, записанный подряд. Иногда весь текст занимает одну строку, иногда в условии описаны несколько строк. Не нужно заранее соединять или разбивать данные: способ хранения будет указан в конкретной задаче.

Строка в Python — это упорядоченная запись символов. Символом будем называть один знак текста: букву, цифру, минус или другой знак. Например, строка АБА-В содержит пять символов, и их порядок важен. Пока мы не преобразовали цифры в числа, значения вроде 7 и 0 остаются знаками текста. Для поиска фрагментов это удобно: мы сравниваем последовательности знаков.

Файл открывают через open, а read() получает его содержимое как одну строку. Метод strip() убирает пробельные символы, например пробелы и переводы строк, только по краям; символы в середине он сохраняет. В этом примере StringIO изображает текстовый файл в памяти, чтобы код можно было сразу запустить. С настоящим файлом чтение устроено так же. Открытие и чтение файла подробно разобраны в уроке мини-курса Python «Читаем данные из файла».

1from io import StringIO2 3with StringIO("АБА-В\n") as file:4    text = file.read().strip()5 6print(text)  # АБА-В

Если в файле записано АБА-В и перевод строки после него, переменная text получит строку с пятью символами. Пробел или перевод строки внутри содержимого останется на месте: удаляются только пробельные символы по краям.

Чтобы проверить, что стоит в определённом месте, пронумеруем символы слева направо. Номер места называется индексом. В Python первая позиция имеет индекс 0, следующая — 1 и так далее. В строке АБВГД буквы стоят на индексах 0, 1, 2, 3 и 4.

Несколько символов, стоящих подряд, образуют непрерывный фрагмент. Например, БВГ — фрагмент строки АБВГД, а БГ — нет: между буквами есть В. В задаче о фрагментах нельзя перескакивать через символы или соединять начало строки с её концом.

Взять фрагмент по границам можно срезом. Запись text[start:end] включает символ с индексом start, но не включает символ с индексом end. Поэтому text[1:4] вернёт БВГ: попадут индексы 1, 2 и 3, а индекс 4 будет правой границей. Индексы и срезы подробнее объясняются в опубликованном уроке Python «Строки: символы, индексы и срезы».

1text = "АБВГД"2fragment = text[1:4]3print(fragment)  # БВГ

Иногда условие относится к двум символам рядом, например к буквам АА. Проверить нужно каждое место, где пара может начаться. В строке длины 5 начала соседней пары — индексы 0, 1, 2 и 3: у каждого справа есть ещё один символ.

Два найденных вхождения могут перекрываться, то есть использовать общий символ. В строке ААА пара АА начинается сначала на индексе 0, затем на индексе 1. Вхождения занимают позиции 0–1 и 1–2; средняя буква участвует в обоих. Это два вхождения, а не одно.

Запись range(len(text) - 1) даёт все возможные начала пары: правая граница range не включается, поэтому последним началом становится предпоследняя позиция. Функция len(text) сообщает число символов в строке, а цикл повторяет проверку для каждого индекса. Запись count += 1 прибавляет единицу к счётчику. Границы цикла подробно разбираются в уроке Python «for и range».

Слово if начинает проверку: команды внутри отступа выполняются, только когда пара совпала с образцом. Сравнения и ветвление можно повторить в опубликованном уроке Python «Условия: сравнения и выбор из двух вариантов».

1text = "ААА"2pattern = "АА"3count = 04 5for i in range(len(text) - 1):6    if text[i:i + 2] == pattern:7        count += 18 9print(count)  # 2

Представь длинную запись, где одни символы разрешены, а другие прерывают подходящий участок. Например, разрешена только буква А. В строке ААXААА первый участок имеет длину 2, второй — длину 3. Буквы по обе стороны от X нельзя соединить: фрагмент должен быть непрерывным.

Чтобы найти самый длинный участок, достаточно идти слева направо и держать две длины. current — сколько разрешённых символов подряд заканчивается в текущем месте; best — наибольшая длина, которую мы уже встретили. Проверка char in allowed отвечает, входит ли текущий символ в список разрешённых. Разрешённый символ увеличивает текущую длину, запрещённый обнуляет её. После каждого разрешённого символа команда max(a, b) оставляет большее из двух значений. Это постепенный выбор результата, знакомый по уроку Python «Отбор результата».

1text = "ААXААА"2allowed = "А"3current = 04best = 05 6for char in text:7    if char in allowed:8        current += 19        best = max(best, current)10    else:11        current = 012 13print(best)  # 3

В следующем варианте нужно найти самый длинный фрагмент, внутри которого выбранная пара встречается не больше заданного числа раз. «Не более двух» разрешает ноль, одно или два вхождения; третье уже нарушает ограничение. Каждое вхождение пары по-прежнему считаем с перекрытием.

Для этой задачи удобно двигать левую и правую границы окна. Окно — это рассматриваемый непрерывный фрагмент. Мы расширяем его справа на один символ; если число вхождений стало слишком большим, передвигаем левую границу вправо, пока условие снова не выполнится. Окно остаётся непрерывным.

При добавлении правого символа новая пара могла только закончиться на нём. При удалении символа слева проверяем, начиналась ли там пара; если да, уменьшаем счётчик. Это позволяет учитывать перекрывающиеся пары и не пересчитывать весь фрагмент после каждого шага.

Повторять сдвиг слева будем циклом while: он выполняет команды, пока число вхождений превышает предел. Подробный разбор этого цикла есть в опубликованном уроке Python «while: повторяем, пока условие верно».

1text = "ААААБААА"2pattern = "АА"3limit = 24left = 05occurrences = 06best = 07 8for right in range(len(text)):9    if right > 0 and text[right - 1:right + 1] == pattern:10        occurrences += 111 12    while occurrences > limit:13        if text[left:left + 2] == pattern:14            occurrences -= 115        left += 116 17    best = max(best, right - left + 1)18 19print(best)  # 5

Здесь right — индекс только что добавленного символа, а left — индекс первого символа окна. Его длина равна right - left + 1, потому что обе границы входят в него. Левая граница может сдвинуться несколько раз; цикл остановится, когда вхождений снова не больше двух.

Теперь строка содержит запись, похожую на арифметику. Сначала договоримся, какие записи в задачах этого урока считаются допустимыми. Точное правило состава выражения называется грамматикой. Здесь это не правила русского языка, а перечень частей и порядка, в котором они могут стоять.

Число — либо одиночный ноль, либо запись, которая начинается с цифры 6, 7, 8 или 9 и затем может содержать цифры 0, 6, 7, 8 или 9. Поэтому 0 и 760 — числа, а 07 — нет: ноль может быть числом сам по себе, но не началом многозначной записи.

Между числами стоит ровно один знак: вычитание - или умножение *. Это бинарные операторы: каждый соединяет число слева и число справа. Поэтому 7-0 допустимо, а -0 в начале строки — нет: перед минусом нет числа. Выражение не может закончиться оператором.

1examples = ["0", "7-0", "760*8", "07", "-0", "7--8", "7*"]2valid = ["0", "7-0", "760*8"]3for expression in examples:4    print(expression, expression in valid)

Для проверки иди по ожидаемому порядку: число, оператор, число, оператор, число. Бинарный означает, что у знака есть два соседа — левое и правое число. Подробный разбор арифметических выражений, типов чисел и операций есть в опубликованном уроке Python «Числа, типы и арифметические выражения»; здесь дополнительно проверяется допустимая запись цифр.

В большом файле не нужно вырезать и проверять каждый возможный фрагмент: их число быстро растёт. Вместо этого читаем строку слева направо и следим, может ли текущий символ продолжить уже начатое выражение. Фрагмент, который сейчас проверяется, будем называть кандидатом. Когда правило нарушается, незаконченный кандидат сбрасывается. Если на месте ошибки начинается новое число, поиск начинается с него.

Достаточно помнить два признака: ждём ли мы число и состоит ли текущее число только из нуля. После знака ожидается число. Если пришёл оператор или другой посторонний символ, незаконченная часть не подходит. Ноль завершает самостоятельное число, поэтому сразу следующая цифра не может продолжить его: при записи 07 нужно отбросить ноль и начать новый кандидат с цифры 7.

Знак оператора не является окончанием выражения: справа ещё должно встретиться число. Поэтому длину результата обновляем после каждой цифры, которая завершает число. Кандидат 7- имеет длину 2, но запись 7- не является завершённым выражением; число 7 до оператора уже остаётся допустимым выражением длины 1.

В этом проходе нужны и сам символ, и его позиция. Запись enumerate(text) при каждом шаге цикла даёт сразу оба значения: i — индекс символа, а char — символ на этой позиции. Так мы сможем измерить фрагмент от его начала до текущей цифры.

1text = "x7-0*68z07-6*8!"2digits = "06789"3operators = "-*"4expect_number = True5zero_only = False6start = None7best = 08 9for i, char in enumerate(text):10    if char in digits:11        if start is None:12            start = i13            expect_number = False14            zero_only = char == "0"15            best = max(best, 1)16        elif expect_number:17            # Продолжаем выражение после оператора.18            expect_number = False19            zero_only = char == "0"20            best = max(best, i - start + 1)21        elif zero_only:22            # После отдельного нуля нельзя дописать цифру.23            start = i24            zero_only = char == "0"25            best = max(best, 1)26        else:27            best = max(best, i - start + 1)28    elif (char in operators and start is not None29            and not expect_number):30        expect_number = True31        zero_only = False32    else:33        start = None34        expect_number = True35        zero_only = False36 37print(best)  # 6

Переменная start хранит начало текущего кандидата, а признаки говорят, какую часть мы ожидаем. После ошибки новая цифра может начать новый кандидат. Каждый символ рассматривается один раз, поэтому время работы растёт вместе с длиной строки. Такое время называют линейным. Повторить состояние цикла и счётчики можно в опубликованном уроке Python о счётчиках и накопителях.

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

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

Проверку одного фрагмента удобно назвать и вызывать снова для другого. Такая именованная часть программы называется функцией. Запись def is_expression(candidate): задаёт функцию, которая получает проверяемый фрагмент в переменной candidate. Команда return завершает проверку и возвращает True, если запись подходит, или False, если правило нарушено. Создание и вызов функций подробно разбираются в уроке Python «Функции: параметры и возвращаемый результат».

1def is_expression(candidate):2    digits = "06789"3    operators = "-*"4    size = len(candidate)5    if not candidate:6        return False7    if candidate[0] in operators or candidate[-1] in operators:8        return False9 10    expect_number = True11    i = 012    while i < size:13        if expect_number:14            if candidate[i] == "0":15                i += 116                if i < size and candidate[i] in digits:17                    return False18            elif candidate[i] in "6789":19                i += 120                while i < size and candidate[i] in digits:21                    i += 122            else:23                return False24            expect_number = False25        else:26            if candidate[i] not in operators:27                return False28            i += 129            expect_number = True30 31    return not expect_number32 33print(is_expression("7-0"))   # True34print(is_expression("07-6"))  # False

Сверяй именно то, что просит условие: длину фрагмента, число вхождений или значение выражения. В этом уроке ищется длина, а не результат арифметического вычисления. Приём выбора ответа можно повторить в опубликованном уроке Python «Отбор результата».