Стек, или Путешествие туда и обратно

Вторников А. А.

СТЕК,  
или ПУТЕШЕСТВИЕ 
ТУДА И ОБРАТНО

Москва, 2017

УДК 004.6:004.42
ББК 32.972
В87

Вторников А. А.

В87 
Стек, или Путешествие туда и обратно. – М.: ДМК Пресс,
2017. – 140 с.: ил.

ISBN 978-5-97060-517-2

Книгапосвященапростойиудивительноэлегантнойструктуреданных–стеку.

Описаны скобочные структуры, подпрограммы (в том числе рекурсивные), передачапараметров,разборивычислениевыражений,распознаваниепоследовательностей символов. Также рассмотрено описание устройства и реализация простой,
но достаточно мощной стековой машины; приведены многочисленные примеры
программ,атакжесписокзадач,втомчисленетривиальных.Насайтеиздательства
dmkpress.com содержатся дополнительные материалы, среди которых исходные
коды простого транслятора стековой машины (на языке Java).

Изданиепредназначенопреждевсегопытливымстаршеклассникам,студентам

вузов, а также тем, для кого программирование – хобби.

УДК 004.6:004.42
ББК 32.972

Все права защищены. Любая часть этой книги не может быть воспроиз
ведена в какой бы то ни было форме и какими бы то ни было средствами без
письменного разрешения владельцев авторских прав.

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

 
© Вторников А. А., 2017

ISBN 978-5-97060-517-2 
© Оформление, издание, ДМК Пресс, 2017

Содержание

Вместо предисловия .....................................................................................5

Введение ...................................................................................................................6

Часть I. Задачи, приводящие к стеку ..........................................10
Скобочные структуры: элементарный случай .................................................10
Стек: знакомство ........................................................................................................18
Скобочные структуры: общий случай ................................................................24
Подпрограммы: постановка задачи......................................................................28
Подпрограммы: появляется стек ..........................................................................41
Подпрограммы: рекурсия ........................................................................................46
Знакомая незнакомка: арифметика .....................................................................55

Алгоритм трансляции выражений ..................................................................61

Стек как вычислительное устройство ................................................................67
Стековая машина .......................................................................................................70
Подпрограммы: передача параметров .................................................................75
Стек и грамматики .....................................................................................................89
Заключение ..................................................................................................................98

Часть II. От слов – к делу .........................................................................99
Расширенная стековая машина .............................................................................99
Первая программа ...................................................................................................105
Как работает транслятор ......................................................................................108

Класс ToyStackMachine.java ...........................................................................109
Класс OpcodeTable.java ....................................................................................109
Класс SymbolTable.java .....................................................................................111
Класс Assembler.java ...........................................................................................111
Класс StackMachine.java ...................................................................................113
Расширение системы команд ..........................................................................114

Примеры программ .................................................................................................115

Суммирование последовательности чисел ................................................115
Сложение двух чисел (вариант 1) .................................................................116
Сложение двух чисел (вариант 2) .................................................................117

 Содержание

Сложение последовательности чисел в памяти .......................................118
Факториал .............................................................................................................119
Вывод текста ........................................................................................................120
Программа-шутка ..............................................................................................121
Указания по программированию ..................................................................122

К вершинам мастерства ........................................................................................122
Заключение ...............................................................................................................123

Библиография ................................................................................................124

Приложение A. Способы реализации стеков ...................126
Реализация стека на основе массива ................................................................126
Реализация стека на основе связанного списка ...........................................128

Приложение B. Язык Forth ..................................................................131

Приложение C. Стек и современные языки  
программирования ....................................................................................136

Приложение D. Исходные коды транслятора  
и интерпретатора ........................................................................................138

Вместо предисловия

Несмотря на то что почти всякая книга по программированию начинается с предисловия, оно почти всегда пишется последним. Для автора книги это последний шанс оправдать (хотя бы для самого себя) 
и мелкость темы, и убогость стиля, и отсутствие литературного таланта.
Будем честными: предисловия пишут не для того, чтобы их читали. 
Это единственное место, где можно попытаться убедить потенциального читателя потратить свое время и свои деньги на книгу до того, 
как он поймет, что ошибся. Косвенно переложив тем самым ответственность за выбор на него.
Автор убежден, что это не имеет ничего общего с моралью, и поэтому отказывается от ложных оправданий и пустых обещаний. Да, 
он писал книгу не без удовольствия, но вряд ли это может служить 
весомой рекомендацией. Единственный совет, который он может 
предложить, – обратиться к оглавлению, выбрать любой раздел и попробовать почитать. Первое впечатление обычно и самое верное.
Впрочем, одно достоинство у предисловия все-таки есть. В нем 
автор может выразить свою благодарность тем, кто вдохновил его 
на напи сание книги, кто помогал ему дельным советом или добрым 
учас тием, от кого он получал поддержку.
Не воспользоваться этой возможностью было бы верхом черствости. Автор признателен своей семье, в особенности великолепному 
Ламику, но, конечно, больше всех – крошке Ру.

Введение

Программирование богато алгоритмами и структурами данных, и современный программист должен владеть большинством из них. Или, 
по крайней мере, иметь о них ясное представление.
Да, нельзя объять необъятного. И все же есть некий минимум, которым, на наш взгляд, должен владеть всякий программист, чтобы 
считаться профессионалом.
В физике известен второй закон термодинамики. В самой примитивной формулировке он постулирует невозможность вечного двигателя: какие бы ухищрения нами ни предпринимались, невозможно 
направить всю имеющуюся энергию на полезную работу; часть (и порой значительная часть) энергии неизбежно будет теряться. Конечно, 
закона сохранения энергии никто не отменял: сама по себе энергия 
никуда не пропадает, она переходит в другие формы и рассеивается 
в виде тепла. Именно поэтому КПД любого двигателя всегда строго 
меньше единицы. Энергия, которой принципиально нельзя воспользоваться, увеличивает хаос во Вселенной. Количественной мерой этого хаоса (или неупорядоченности) в термодинамике служит энтропия. Задача инженеров – уменьшить энтропию, снизить, насколько 
можно, потери, не дать этой рассеянной энергии еще больше увеличить хаос.
Программирование – это дисциплина на стыке математики и инженерии. Как математики мы, программисты, призваны решать 
сложные задачи, переводить их на язык чисел и символов. Как инженеры – воплощать решения в форме программ, которые могут быть 
выполнены машиной. Кроме того, мы должны обеспечивать эффективность выполнения этих программ. Эффективность – это не только 
скорость, с которой задача будет решена, но также и объем занимаемой памяти. Разумеется, к инженерным «заботам» следует отнести 
масштабируемость, расширяемость, устойчивость, возможность внесения изменений и проч.
Математик работает так, как будто у него в запасе вечность и неограниченные ресурсы. Если для решения задачи программе придется 
проработать пусть даже миллион лет, математик будет считать свою 
миссию выполненной. Инженер, напротив, скован массой технических 
и экономических ограничений. Миллион лет его никак не устраи вает: 

Введение  7

хорошо – час, может быть – день, в крайнем случае – месяц. Если инженер не может обеспечить этого, то либо задача признается (в данных условиях) нерешенной, после чего она возвращается математику 
для дальнейших раздумий, либо возникают сомнения, и часто обоснованные, в том, что инженер вообще способен это сделать. 
Программист – это, как правило, немного математик, а в основном 
инженер (многие, очень многие из тех, кто считает себя программистами, совсем не понимают самой необходимой математики; может, 
это и чересчур, но вряд ли имеют право так себя именовать). И большую часть времени программист занимается второй, т. е. инженерной, 
стороной деятельности.
Без надежных и удобных инструментов любая деятельность, а инженерная – в особенности, неэффективна и даже невозможна. Математика снабжает нас идеями, концепциями и рецептами (в программировании обычно говорят об алгоритмах), но именно инструментарий 
делает нас сильными, позволяет воплощать идеи, концепции и рецепты в работающие программы. У хорошего мастера, в какой бы области 
он не трудился, есть свой набор инструментов: у любого плотника мы 
найдем пилу, рубанок и стамеску; электрик не может обойтись без отвертки, плоскогубцев и изоленты, а строителю необходимы лопата, 
мастерок и рулетка. А всем им необходим молоток.
Программисту тоже необходимы инструменты. Понятно, первый 
из них – компьютер. Но без программ компьютер бесполезен (разве 
что обогревать пространство вокруг себя, увеличивая энтропию Вселенной). А программы – это не только машинные коды, способные 
выполняться процессором, но и данные, обычно организованные особым образом. Если программист действительно хочет быть профессионалом, а не поденщиком, он должен иметь  ясное представление 
о способах представления данных, понимать, когда их применять, 
и уметь ими пользоваться.
Одной из таких структур данных – стеку – и посвящена эта небольшая книга. Стек давно известен и заслуженно пользуется уважением; 
без него сегодня немыслимо написать ни одной программы. Порой 
стек используется явно, но куда чаще он действует скрытно, в глубине. И надо признать, именно эта – неочевидная – часть возможностей 
остается для многих программистов terra incognita. Очень жаль...
Программисты в своей ежедневной работе полагаются на операционные системы, средства разработки, языки программирования. 
Это – часть их инструментария, в котором также используется стек. 
Конечно, можно было бы сказать: «Для чего мне знать что-то еще? До

 Введение

статочно того, что это работает и этому можно доверять». Да, такой 
взгляд имеет право на существование. До тех пор, пока мы решаем типовые задачи (а для большинства такие задачи – единственное, чем им 
приходится заниматься всю профессиональную карьеру), большего 
и не нужно. Но программирование неизмеримо богаче. В нем полнымполно задач нерешенных, решенных частично либо решенных плохо 
и ждущих своего часа. Стоит ли сознательно обеднять себя и обманываться тем, что можно обойтись имеющимся? Или ждать, когда кто-то 
более умный и отважный сделает то, что считалось невыполнимым?
Конечно, каждый решает этот вопрос по-своему. Но отвергнуть, 
даже не попробовав, никуда не годится.
Изложение в книге построено следующим образом. Стек не возникает неизвестно как, откуда и для чего. В книге рассматривается ряд 
задач нарастающей сложности. Все эти задачи рано или поздно приводят к стеку; таким образом, всякий раз появление стека подготавливается и обосновывается. Для того чтобы читатель мог составить 
себе наиболее полное представление о стеке и его возможностях, часто приводится решение исходной задачи другими способами. Такое 
сравнение всегда полезно, поскольку позволяет оценить достоинства 
и недостатки различных подходов и выбрать из них лучший.
Книгу лучше читать по порядку, поскольку последующий материал обычно опирается на предыдущий. Там, где это представлялось полезным, более ранний материал частично повторяется; это избавляет от необходимости возвращаться назад и позволяет поддерживать 
определенный ритм.
Структурно книга состоит из трех частей. Первая часть – основная. Именно здесь ставятся, обсуждаются и решаются задачи. Вторая часть посвящена описанию небольшой, но достаточно мощной, 
стековой машины и программированию для нее. Третья часть – это 
приложения, среди которых – исходные коды транслятора и интерпретатора стековой машины, описанной во второй части.
Завершается книга библиографией. Мы приложили все усилия 
к тому, чтобы перечислить в ней действительно ценные (на наш 
взгляд) и в то же время доступные источники, относящиеся к основной теме книги.
Эти источники позволят заинтересованным читателям двигаться 
дальше – к настоящим высотам.
В ежедневной практике программиста стек в явном виде встречается лишь иногда; большей частью стек «трудится» незаметно. Чаще 
всего он напоминает о себе тогда, когда работа программы внезапно 

Введение  9

прекращается и на экран (либо в консоль) выводятся малопонятные 
непосвященному строчки сообщений, состоящие из адресов памяти 
и имен функций, вызовы которых привели к остановке. Как правило, 
такие сообщения свидетельствуют о том, что в программах имеются 
ошибки. Эти ошибки обычно невозможно отследить на этапе трансляции программы; они проявляют себя во время исполнения. Многие 
(возможно, большинство) не понимают ни причин их возникновения, 
ни того, что они означают. Прочитав книгу, вы начнете понимать, отчего это происходит и что нужно делать, чтобы программы стали более надежными и устойчивыми.
Основная область применения стеков – трансляция языков программирования и поддержка сред исполнения. Эти области информатики считаются сложными, и это действительно так. Но даже самые 
сложные вещи состоят из простых. Вот этими, относительно простыми вещами мы займемся и коснемся многого, что непосредственно 
используется при реализации языков программирования и работы 
программ после их запуска на исполнение. Если когда-нибудь вам 
придется (или захочется) реализовать язык программирования, то 
будьте уверены – стек станет вашим главным помощником. 
И последнее. Стек в качестве главного «героя» был выбран не случайно. Он по-своему красив. Правда, для того чтобы это оценить, придется потрудиться. Нельзя понять музыку, читая рецензии; музыку 
надо слушать. То же и со стеком – с ним надо поработать. В основном 
тексте книги почти нет привычных задач и упражнений; упражнением в известном смысле является весь текст. Если читатель попробует 
свои силы в реализации задач, которые рассматриваются в книге, – 
это лучшее, чего можно пожелать. Польза будет несомненной.
Кое-где в тексте в качестве иллюстрации тех или иных понятий 
встречаются фрагменты программ, написанных на языке программирования Java. Все они очень просты, и даже если читатель незнаком 
с Java, мы уверены, что он без труда их поймет.
Мы нигде не используем примечаний: ни подстрочных, ни вынесенных в отдельный раздел. Многие склонны их рассматривать как 
малозначительные отступления и обычно пропускают. Кроме того, 
такие примечания прерывают процесс чтения и вынуждают отвлекаться от основной темы. Мы сделали примечания частью текста, выделяя их курсивом. Не стоит их игнорировать – в них много полезной 
информации.

Часть I

Задачи, 
приводящие к стеку

Скобочные структуры: 
элементарный случай

Мы начнем с того, что рассмотрим одну простую задачу, которая послужит отправной точкой всего последующего изложения. Эта задача 
встречается в разнообразных вариантах (и чуть позже мы расскажем 
об этом подробнее), но нам пока вполне достаточно такой формулировки: определить – правильно ли расставлены скобки в произвольном алгебраическом выражении. Несколько примеров даст представление о том, что мы имеем в виду и какое решение ищем:

a + (b * c /(d – e))
a + (b * c /d – e)
(a + b – c * (d / (e + f)))

Если всем входящим в эти выражения переменным (a, b, ...) придать определенные числовые значения, то эти выражения могут быть 
вычислены по правилам элементарной арифметики (конечно, исключая случаи, когда знаменатели дробей обратятся в 0). В этих примерах 
выражений скобки расставлены правильно. Чтобы сделать последнее 
утверждение более наглядным, давайте оставим только скобки, убрав 
все «лишнее»; в результате у нас получится следующее:

(())
()
((()))

Скобочные структуры: элементарный случай  11

Такого рода выражения будем называть скобочными структурами; мы полностью игнорируем все то, что содержится внутри скобок, 
и сосредоточиваем внимание только на скобках и их взаимном расположении. Все приведенные выше скобочные структуры, очевидно, 
корректны, т. е. сформированы правильно. Теперь приведем несколько примеров некорректных (неправильно сформированных) скобочных структур:

(()
())
)(

Давайте немного остановимся на последних примерах и проанализируем, что именно делает эти скобочные структуры некорректными 
(ошибочными или неправильно сформированными). Для этого удобно называть левые скобки «(» открывающими, а правые «)» – закрывающими.
В первом примере число открывающих скобок больше числа закрывающих. Во втором примере ситуация противоположная – число 
открывающих скобок меньше числа закрывающих. В таких случаях 
говорят, что скобки не сбалансированы по числу вхождений. Третий 
пример демонстрирует еще один случай: число открывающих скобок 
совпадает с числом закрывающих (т. е. скобки сбалансированы по 
числу вхождений), но скобочная структура тем не менее ошибочна – 
выражение не может начинаться с закрывающей скобки или заканчиваться открывающей.
Наша ближайшая задача – найти способ (алгоритм) проверки любой заданной скобочной структуры, состоящей только из скобок одного типа (в данном случае скобочной структуры, состоящей только 
из круглых скобок).
Очевидно, что существует бесконечное количество как правильно, 
так и неправильно сформированных скобочных структур. Поэтому 
попытка описать все возможные варианты скобочных структур их 
простым перечислением не осуществима даже теоретически – рано 
или поздно встретится такая скобочная структура, которая не была 
нами предусмотрена. В таком случае программа, осуществляющая 
проверку скобочной структуры, будет не в состоянии определить 
ее правильность. Следовательно, нужен иной способ. Такой способ 
(и очень простой) существует, но, перед тем как описывать его, мы 
предлагаем читателю немного подумать и попытаться найти его самостоятельно.

 Задачи, приводящие к стеку 

Если последовательность скобок начинается с закрывающей или 
завершается открывающей скобкой (наш третий пример), то, бесспорно, такая скобочная структура сформирована неправильно. Но 
эти два предельных случая не позволяют решить задачу в общем 
виде, т. к. первые примеры неправильно сформированных скобочных 
структур начинаются и завершаются нужными видами скобок – соответственно «(» и «)», но которые тем не менее ошибочны.
Итак, в решении задачи мы пока почти никуда не продвинулись. 
Но давайте посмотрим на проблему чуть иначе. Отвлечемся на несколько минут от скобок. Представьте лифт. Во избежание аварии 
необходимо контролировать массу груза (включая людей), перевозимого лифтом. Для этого в лифт встраивается специальный датчик. 
Каждый внесенный груз или входящий человек увеличивает общую 
массу груза в кабине и нагрузку на тросы и лебедку лифта. Разумеется, показания датчика увеличиваются. Каждый выходящий из кабины лифта уменьшает массу груза в кабине, и показания датчика 
уменьшаются.
Наш «груз» – это два вида скобок. Открывающая скобка увеличивает «массу», а закрывающая – уменьшает. Конечно, как и всякая 
аналогия, наш пример страдает неточностями и упрощениями, но он 
тем не менее наводит на идею.
Припишем каждой скобке некий «вес»: открывающей скобке – положительное число (скажем, 1), а закрывающей – число, равное по 
абсолютной величине, но противоположное по знаку (т. е. –1). Датчиком пусть будет целочисленная переменная (назовем ее, например, 
count) с начальным значением, равным 0 (в примере с лифтом это 
означает, что изначально кабина пуста). Эта переменная будет играть 
роль счетчика. Промоделируем поведение нашей «системы» на самой 
простой скобочной структуре: (). Для компактности будем представлять отдельные состояния в виде таблицы, в левой колонке которой 
указывается уже прочитанная часть скобочной структуры, а в правой 
(в той же строке) – значение счетчика. Получаем следующий протокол разбора:

Прочитанная часть   Счетчик
                       0
(                      1
()                     0

В самом начале (когда еще ни одна скобка не прочитана) счетчик 
равен 0. После обнаружения открывающей скобки соответствующее