Стек, или Путешествие туда и обратно (2000,00 руб.)

Стр.3

Стр.4

Стр.5

УДК 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

Стр.3

Содержание Вместо предисловия .....................................................................................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

Стр.4

4  Содержание Сложение последовательности чисел в памяти .......................................118 Факториал .............................................................................................................119 Вывод текста ........................................................................................................ 120 Программа-шутка .............................................................................................. 121 Указания по программированию .................................................................. 122 К вершинам мастерства ........................................................................................ 122 Заключение ............................................................................................................... 123 Библиография ................................................................................................ 124 Приложение A. Способы реализации стеков ................... 126 Реализация стека на основе массива ................................................................ 126 Реализация стека на основе связанного списка ........................................... 128 Приложение B. Язык Forth .................................................................. 131 Приложение C. Стек и современные языки программирования .................................................................................... 136 Приложение D. Исходные коды транслятора и интерпретатора ........................................................................................ 138

Стр.5