DATA·II Структуры данных Глава 15 из 65
Стек, очередь и калькулятор
Глава-сборка: деталь за деталью собираем калькулятор. Сначала он считает, как карманный HP-35 1972 года, у которого не было кнопки «=», потом по рецепту Дейкстры учится скобкам и старшинству операций. По дороге выясняется, что внутри Python работает такой же калькулятор, а очередь нажатий клавиш ходит по кругу.
Структуры данных
- 13 Сложность
- 14 Массивы
- 15 Стек и очередь вы здесь
- 16 Хеш-таблицы
- 17 Деревья
- 18 Кучи
- 19 Графы
Опирается на: 14 · Как список лежит в памяти
Что вы унесёте из главы
- узнавать задачи, где нужен стек, и писать «отменить», проверку скобок и обход без рекурсии
- переводить обычные выражения в обратную польскую запись и вычислять их — то есть написать свой калькулятор
- выбирать между стеком, очередью и деком и строить очередь на кольцевом буфере
В конце прошлой главы мы заметили, что многие вещи помнят последнее первым. Кнопка «Назад» в браузере возвращает на страницу, открытую последней. Ctrl+Z отменяет последнее действие, потом предпоследнее. Функции возвращаются в порядке, обратном вызовам. Нужное устройство у нас уже есть: список, у которого мы трогаем только конец, а с конца, как мы выяснили, и добавлять, и забирать стоит $O(1)$.
Из таких устройств мы соберём работающую вещь — калькулятор. Он поймёт 2 * (3 + 4) - 5 со скобками и старшинством операций, сообщит, если скобки расставлены неправильно, а нажатия клавиш будет держать в очереди, которая ходит по кругу. Деталей в нём пять, и каждая — структура данных.
Деталь первая: стопка
Представьте стопку тарелок в столовой. Чистую тарелку кладут сверху, берут тоже сверху. Добраться до нижней, не сняв верхние, нельзя. Последняя положенная уходит первой — по-английски это называют LIFO, last in, first out.
Такая дисциплина и называется стеком, от английского stack — стопка. Операций у стека три: положить на вершину (push), снять с вершины (pop) и посмотреть, что на вершине, не снимая (peek). Больше ничего: ни чтения по номеру, ни вставки в середину. В бедности интерфейса и весь смысл: программа, которая пользуется стеком, гарантированно не залезет в середину и не перепутает порядок.
В Python отдельного типа «стек» нет: стеком служит обычный список. append кладёт на вершину, pop() снимает, a[-1] подглядывает — и всё это $O(1)$, потому что вершина стека — конец массива, где есть запас и ничего не надо сдвигать. Вот самая знакомая всем стопка — кнопка «Отменить».
Каждое действие перед тем, как изменить текст, кладёт на стопку прежнее состояние. Ctrl+Z снимает верхнее — и откатывает ровно одно действие, самое свежее. Нажмите «Шаги»: видно, как стопка undo растёт на трёх словах и худеет на двух отменах.
В описании стека нет ни слова о том, как он устроен внутри. Его можно собрать на массиве, как здесь, а можно на связном списке из прошлой главы — вершиной будет голова, и push с pop тоже станут $O(1)$. Описание структуры через операции, без устройства, называют абстрактным типом данных. Стек, очередь, словарь — абстрактные типы; массив и связный список — способы их сделать.
Назад и вперёд
Кнопок в браузере две, «Назад» и «Вперёд», и стопок тоже две. Когда вы уходите назад, текущая страница не пропадает: она ложится на стопку «вперёд». А что происходит со стопкой «вперёд», если, вернувшись назад, вы щёлкнете по новой ссылке? Попробуйте угадать, прежде чем проверить.
Новая ссылка очищает стопку «вперёд» до дна: будущее, от которого вы отказались, исчезает. Поэтому и в текстовом редакторе после отмены и нового ввода повтор (Ctrl+Y) больше ничего не возвращает.
Стопка, которая у вас уже была
Со стеком вы работаете с главы 5, только там он назывался стеком вызовов. Вызов функции кладёт на стопку кадр, возврат снимает. Функция, которую позвали последней, заканчивает первой — LIFO в чистом виде. А переполнение стека, на которое мы наткнулись в главе 9, — это стопка, выросшая выше разрешённого.
Там же, в главе 9, мы говорили: любую рекурсию можно переписать циклом, но тогда стопку недоделанных дел придётся хранить самим. Теперь это нам по силам. Вот разворачивание вложенных списков из той главы — без единого рекурсивного вызова, на своём стеке.
Свой стек живёт в обычном списке, и предел у него один — память. Стек вызовов ограничен тысячей кадров. А reversed нужен вот зачем: стопка отдаёт последнее положенное первым, и чтобы первым достать первый элемент, класть приходится с конца.
Деталь вторая: калькулятор без «=»
Зачем инженерам HP понадобилась такая клавиатура, видно на выражении $(3 + 4) \times (5 + 6)$. Обычный калькулятор, пока считает вторую скобку, должен помнить про отложенное умножение и знать, что умножение старше сложения. Запись «сначала числа, потом действие» этих забот не знает. В ней выражение выглядит так:
$$3\ \ 4\ \ +\ \ 5\ \ 6\ \ +\ \ \times$$Правило вычисления одно. Читаем слева направо. Число кладём на стек. Знак операции снимает со стека два верхних числа, применяет к ним действие и кладёт результат обратно. Три, четыре — на стеке два числа. Плюс превращает их в семь. Пять, шесть — на стеке семь, пять, шесть. Плюс — семь и одиннадцать. Умножение — семьдесят семь. Ни скобок, ни старшинства: порядок действий записан самим порядком символов.
Такая запись называется обратной польской, сокращённо ОПЗ, а привычная, где знак стоит между числами, — инфиксной. Попробуйте посчитать на калькуляторе ниже: он ведёт себя как HP-35, только стек у него на виду.
Калькулятор в десять строк
Правило вычисления ОПЗ переводится в Python почти дословно. Операции удобно держать в словаре, где значения — функции-лямбды из главы 10.
Одна тонкость: со стека первым снимается второй операнд. Для сложения и умножения порядок не важен, а вот 8 3 - должно дать пять, а не минус пять. Проверьте сами, поменяв местами a и b.
Этот калькулятор доверчив. Дайте ему 3 + — и stack.pop() упадёт с IndexError, сообщением, которое ничего не скажет пользователю. Дайте 3 4 — и он молча вернёт четыре, забыв про тройку. Научить его отличать правильную запись от неправильной — первая задача главы, eval-rpn; пригодится raise из главы 11.
Деталь третья: скобки на месте?
Обратная польская запись хороша для машины, но люди пишут 2 * (3 + 4). Калькулятор для людей должен понимать скобки, и первым делом — проверять, что они расставлены правильно. Для круглых скобок хватило бы счётчика: открывающая прибавляет единицу, закрывающая отнимает, и счётчик не должен уходить в минус и обязан кончить нулём. Но в выражениях и программах бывают и квадратные, и фигурные, и тогда счётчики не спасают: в строке ([)] каждый вид скобок по отдельности в порядке, а вместе — бессмыслица.
Верное правило другое: закрывающая скобка должна закрывать последнюю ещё не закрытую открывающую. Раз последнюю, значит, нужен стек.
Именно так проверяет скобки сам Python, прежде чем выполнить программу. В главе 1 он жаловался на незакрытую кавычку; со скобками он ещё разговорчивее. Запустите ячейку и проверьте, какую из скобок он назовёт.
«Закрывающая круглая скобка не подходит к открывающей квадратной»: в нашей функции это миг, когда stack.pop() вернул не ту скобку. Подсветка парной скобки в редакторе кода работает так же. В задаче balanced мы научим функцию показывать, где ошибка, и не путаться в скобках внутри строк, как не путается в них интерпретатор.
Деталь четвёртая: сортировочная станция
Инфиксное выражение — это состав вагонов: числа вперемешку со знаками операций. Его надо переставить в обратную польскую запись, где каждый знак стоит после своих чисел. На станции три пути: входящий справа, выходной слева и тупик, уходящий вниз. Числа проходят на выход сразу, не задерживаясь. Знаки операций заезжают в тупик и ждут, а тупик — это стек: выехать из него может только последний заехавший.
Всё искусство — в том, когда выпускать знаки из тупика. Пусть на входе 3 + 4 * 2. Тройка уходит на выход, плюс — в тупик, четвёрка — на выход. Теперь подходит умножение. Оно старше сложения, значит, должно выполниться раньше, то есть в ОПЗ стоять раньше плюса. Поэтому плюс остаётся ждать, а умножение заезжает в тупик поверх него. Двойка — на выход, вход кончился, тупик опустошается сверху: сначала умножение, потом плюс. Получилось 3 4 2 * +.
Вот все правила станции. Число — сразу на выход. Знак операции сначала выпускает из тупика все знаки, которые старше его или равны ему по старшинству, и только потом заезжает сам. Открывающая скобка заезжает в тупик и служит стенкой: знаки за неё не выезжают. Закрывающая выпускает всё до открывающей, и обе скобки исчезают. Когда вход кончился, тупик выпускает всё, что в нём осталось. Этот рецепт называют алгоритмом сортировочной станции.
Равных по старшинству из тупика тоже выпускают, и причину видно на 8 - 3 - 2. Вычитание выполняется слева направо: $(8 - 3) - 2 = 3$. Значит, первый минус должен попасть в ОПЗ раньше второго: 8 3 - 2 -. Если бы равные не выпускались, получилось бы 8 3 2 - -, то есть $8 - (3 - 2) = 7$. Сравните на станции 8 - 3 - 2 и 8 - (3 - 2).
Каждый токен заезжает в тупик и выезжает из него не больше одного раза, поэтому вся станция работает за $O(n)$ — один проход по выражению, как и вычисление ОПЗ.
А если степень?
В главе 1 мы видели, что 2 ** 3 ** 2 равно 512: степени считаются справа налево, $2^{(3^2)}$. Для станции это значит, что при равном старшинстве две степени не выпускают друг друга из тупика — иначе получилось бы $(2^3)^2 = 64$. Знаки, которые выполняются справа налево, называют правоассоциативными, и для них сравнение «старше или равен» превращается в «строго старше». Научить станцию степени — третья задача главы. Унарный минус, как в -2 ** 2, — ещё одна ловушка: его приходится отличать от вычитания по тому, что стоит слева.
Калькулятор в сборе
Осталась мелочь: превратить строку "2*(3+4)" в список токенов. Цифры, идущие подряд, склеиваем в число, знаки и скобки становятся отдельными токенами, пробелы пропускаем. Остаётся соединить три детали одну за другой.
Шестьдесят строк — и у вас калькулятор, который понимает скобки и старшинство. Разбиение текста на токены, перевод в удобную для машины форму и вычисление на стеке — это в миниатюре устройство любого интерпретатора. В главе 50 мы построим разборщик для целого языка, а в главе 51 — интерпретатор.
Калькулятор внутри Python
Python считает выражения так же, как HP-35. Прежде чем выполнить программу, он переводит её в команды для своей виртуальной машины, а машина эта — стековая. Модуль dis показывает эти команды.
Прочитайте столбец команд сверху вниз: положить a, положить b, сложить, положить c, умножить. Это a b + c * — обратная польская запись. LOAD кладёт значение на стек, BINARY_OP снимает два верхних и кладёт результат. Каждый раз, когда вы запускаете ячейку в этом курсе, на сервере считает стековая машина, дальняя родственница карманного HP-35. Подробнее заглянем в эти команды в главе 33.
Деталь пятая: очередь нажатий
Калькулятор собран, но у него появилась новая забота. Пальцы бывают быстрее программы: пока она считает, человек успевает нажать ещё три клавиши. Терять их нельзя, а обработать надо в том порядке, в котором нажимали. Стек тут не годится — он вернул бы последнее нажатие первым. Нужна очередь: первым пришёл — первым ушёл, по-английски FIFO, first in, first out.
Сделать очередь на списке легко и неправильно: append в хвост, pop(0) из головы. Мы уже знаем, что pop(0) сдвигает все оставшиеся элементы и стоит $O(n)$, а в гонке прошлой главы видели, как это выглядит на ста тысячах. Очередь на list.pop(0) — классическая причина медленных программ на Python. Правильный инструмент мы тоже уже видели — collections.deque.
Слово deque — сокращение от double-ended queue, по-русски дек: очередь, у которой оба конца рабочие. Дек умеет быть и стеком (работаем с одним концом), и очередью (кладём в один, берём из другого).
Очередь по кругу
В самом компьютере, где нет ни deque, ни сборщика мусора, а память под очередь выделена раз и навсегда, нажатия складывают в кольцевой буфер. Возьмём массив постоянной длины и два номера: голову, откуда забирать, и хвост, куда класть. Положили — хвост сдвинулся на ячейку. Забрали — сдвинулась голова. Никто никуда не переезжает. А когда хвост доходит до конца массива, он перескакивает в начало, на ячейки, которые голова уже освободила: массив свёрнут в кольцо, и номер следующей ячейки — остаток от деления на длину.
После двух pop и двух push массив выглядит странно: ['Е', 'Т', 'И', 'В']. Но голова стоит на ячейке 2, и если читать от неё по кругу, получается «ИВЕТ», в том порядке, в каком нажимали. Последняя строка показывает переполнение: пятое нажатие не поместилось, push вернул False. Поле size заведено не для красоты. Одних головы и хвоста мало: когда они совпадают, буфер может быть и пустым, и полным. Поэтому либо хранят размер, как здесь, либо держат одну ячейку всегда свободной — тогда «голова равна хвосту» значит только «пусто».
В IBM PC под очередь нажатий BIOS отводила 32 байта — шестнадцать ячеек по два байта — и два указателя, на голову и хвост; совпали указатели — очередь пуста. Тот же приём живёт в звуковых картах, сетевых адаптерах и журналах событий: везде, где поток данных идёт без остановки, а память ограничена.
Очередь из двух стопок
Последняя деталь — головоломка. Допустим, у вас есть только стеки, а нужна очередь. Её можно собрать из двух стопок. Новые элементы кладём на первую, «вход». Забираем со второй, «выход». А когда выход пуст, перекладываем на него весь вход — и порядок переворачивается: самый старый элемент оказывается сверху.
Перекладывание бывает долгим — $O(n)$ за раз. Но вспомните монетки из прошлой главы. Каждый элемент за всю жизнь кладётся на вход один раз, перекладывается на выход один раз и снимается с выхода один раз. Три действия на элемент, сколько бы их ни было, — значит, каждая операция очереди стоит $O(1)$ амортизированно. Собрать такую очередь — последняя задача главы. У головоломки есть и практический смысл: в функциональных языках, где самая дешёвая структура — неизменяемый список-стопка, очереди делают именно так.
Какую структуру взять для каждой задачи: (1) проверить, правильно ли закрыты теги в HTML-странице; (2) обслуживать запросы к серверу в порядке поступления; (3) хранить последние 50 действий для «Отменить», выбрасывая самые старые?
Теги — как скобки: закрываться должен последний открытый, нужен стек. Запросы — в порядке поступления: очередь. Отмена с ограниченной памятью — стек с одной стороны и выбрасывание старого с другой: дек с maxlen=50. Так можно устроить историю отмен с ограниченной глубиной.
Задачи
Четыре детали калькулятора, каждую надо довести до ума: научить замечать ошибки, понимать степень и не путаться в кавычках. Тесты проверяют и края — пустой ввод, одну скобку, длинные выражения.
Напишите eval_rpn(expr): вычислить выражение в обратной польской записи, где токены разделены пробелами. Числа — целые или дробные, могут быть отрицательными (-3, 2.5); операции — + - * /. Если запись неправильная — операции не хватает чисел, в конце на стеке осталось не одно число, попался непонятный токен или строка пустая, — поднимите ValueError с понятным сообщением.
Перед тем как снимать два операнда, проверьте len(stack) < 2. После цикла проверьте, что на стеке ровно одно число.
Непонятный токен: float("abc") сам поднимает ValueError, но с сообщением на английском про float. Лучше поймать его try/except и поднять свой ValueError с понятным текстом.
Число -3 не путается с операцией минус: split оставляет его одним токеном "-3", а такого ключа в OPS нет. На HP-35 для этого была отдельная клавиша смены знака, CHS: знак числа и вычитание — разные вещи.
Напишите bracket_error(code), которая проверяет скобки () [] {} в строке программы и возвращает -1, если всё в порядке, а иначе — индекс ошибки, похожий на тот, что Python показывает в сообщении SyntaxError:
- закрывающая скобка, которой нечего закрывать или которая не подходит к последней открытой, — её индекс;
- если строка кончилась, а скобки остались незакрытыми, — индекс самой первой незакрытой (Python в этом случае показывает последнюю).
Подвох: скобки внутри строковых литералов — между двумя одинарными или двумя двойными кавычками — не считаются. В print(")") всё в порядке. Кавычки внутри кавычек другого вида — обычные символы; экранирования \" в тестах нет.
Чтобы вернуть индекс незакрытой скобки, на стеке надо хранить не только саму скобку, но и её индекс: stack.append((ch, i)). Самая первая незакрытая лежит на дне стека.
Для кавычек заведите переменную quote: None, если вы вне строки, или сам символ кавычки, если внутри. Внутри строки всё, кроме такой же кавычки, пропускайте.
Переменная quote — маленький автомат с тремя состояниями: «вне строки», «в строке с одинарными кавычками», «в строке с двойными». Python разбирает текст программы таким же автоматом, только состояний у него больше: экранирование, тройные кавычки, комментарии. Автоматы ждут нас в главе 54.
Напишите to_rpn(expr), которая принимает строку с инфиксным выражением и возвращает список токенов в обратной польской записи. В выражении — неотрицательные целые числа (возможно, многозначные), операции + - * / **, скобки и пробелы в любом количестве. Старшинство как в Python: ** старше * /, те старше + -; ** выполняется справа налево, остальные — слева направо. Если скобки не парные — ValueError.
Пример: to_rpn("2*(3+4)**2") → ['2', '3', '4', '+', '2', '**', '*'], а to_rpn("2 ** 3 ** 2") → ['2', '3', '2', '**', '**'].
Сначала токенизатор: сейчас ** превращается в два токена *. Встретив звёздочку, посмотрите на следующий символ.
Для ** условие выпуска из тупика другое: выпускать только строго старшие знаки, а равные оставлять. Удобно завести множество правоассоциативных знаков RIGHT = {"**"}.
Непарные скобки: закрывающая, для которой в тупике нет открывающей, — ошибка; открывающая, оставшаяся в тупике в конце, — тоже.
Вся разница между левой и правой ассоциативностью — одно сравнение: «старше или равен» против «строго старше». А в ALGOL 60, для которого Дейкстра и придумал станцию, степень выполнялась слева направо: 2↑3↑2 там означало $(2^3)^2 = 64$. Порядок действий — договорённость языка, а не закон природы.
Напишите класс Queue с методами push(x), pop() (забрать самый старый; у пустой — IndexError) и __len__. Внутри разрешены только два списка, которые используются как стеки: только append, pop() без аргумента, len и проверка на пустоту. Никаких pop(0), insert, срезов и deque. Тесты смешивают полтораста тысяч операций с ограничением по времени.
Забирать всегда из outbox. Если он пуст — переложите в него всё из inbox, снимая по одному с вершины.
Перекладывать надо только когда outbox пуст, а не при каждом pop. Иначе порядок испортится, а время станет квадратичным.
Каждый элемент проходит путь «в inbox → в outbox → наружу» ровно один раз, поэтому $n$ операций стоят $O(n)$ в сумме, хотя отдельный pop иногда перекладывает тысячи элементов. Это та же амортизация, что у append в списке: дорогие шаги редки и оплачены заранее.
Куда дальше
У HP-35 была ещё одна клавиша — STO: она сохраняла число в отдельную ячейку памяти, чтобы потом достать его по RCL. Ячейка была одна. Захотим, чтобы наш калькулятор помнил переменные по именам — x = 5, rate = 0.07, — и их станет много. В списке пар «имя — значение» поиск имени стоит $O(n)$: на миллионе переменных каждое обращение перебирало бы миллион записей. Ни стек, ни очередь, ни массив не умеют находить по имени. А словарь Python находит имя среди миллиона за одну операцию. В следующей главе мы построим такую структуру сами, а потом попробуем её сломать.