Учим стек вычислять

Уважаемые читатели!

У газеты-вкладки “В мир информатики” появился свой электронный адрес: vmi@1september.ru.

В предыдущей публикации [1] был описан так называемый “стек” — структура данных, в которой реализован принцип “последним пришел — первым вышел” (по-английски — “Last In First Out”, или LIFO), и разработаны четыре вспомогательных алгоритма для работы со стеком, который моделировался в виде массива:

— Поместить — размещение в стеке нового числа num;

— Извлечь — извлечение числа из стека (извлекаемое число является результатом алгоритма-функции);

— Вершина — функция, возвращающая число на вершине стека (само число из стека не извлекается);

— Очистка — заполнение стека нулями.

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

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

1) извлечь из стека число x;

2) достать из стека число y;

3) выполнить требуемую операцию по правилу: y операция x ;

4) поместить результат операции в стек.

Подготовим первый алгоритм, выполняющий сложение чисел:

алг Сложить

нач цел n

· если top > 1

· · то

· · · |Извлекаем число

|на вершине стека

· · ? |и присваиваем его

|значение величине n

· · · |Здесь и далее используем

|разработанные ранее

· · · |вспомогательные алгоритмы

· · · n := Извлечь

· · · |Извлекаем число на вершине стека,

· · · |складываем его значение с величиной n

· · · |и присваиваем результат величине n

· · · n := Извлечь + n

· · · |Размещаем сумму в стеке

· · · Поместить(n)

· · иначе

· · · вывод нс, "Стек содержит только одно число!"

· все

кон

Аналогично работают и другие алгоритмы:

алг Вычесть

нач цел n

· если top > 1

· · то

· · · n := Извлечь

· · · n := Извлечь - n

· · · Поместить(n)

· · иначе

· · · вывод нс, "Стек содержит только одно число!"

· все

кон

алг Умножить

нач цел n

· если top > 1

· · то

· · · n := Извлечь

· · · n := Извлечь * n

· · · Поместить(n)

· · иначе

· · · вывод, нс, "Стек содержит только одно число!"

· все

кон

алг Разделить |Нацело

нач цел n

· если top > 1

· · то

· · · n := Извлечь

· · · n := div(Извлечь, n)

· · · Поместить(n)

· · иначе

· · · вывод нс, "Стек содержит только одно число!"

· все

кон

— где div — функция, возвращающая целочисленное частное от деления своего первого аргумента на второй (в других языках программирования для получения такого результата используется не функция, а специальная операция).

Прежде чем идти дальше, заметим, что в наших алгоритмах мы использовали вызовы уже написанных ранее алгоритмов, в частности, алгоритмов Поместить и Извлечь . Данный прием является хорошим правилом — использовать уже написанный код при разработке новых алгоритмов и программ. Наши новые алгоритмы стали намного “прозрачнее” и легко читаемыми, ведь всю работу по извлечению числа из стека и помещению его в стек выполняют вспомогательные алгоритмы, которые мы уже написали и для которых выполнили отладку. Такая технология называется программированием снизу вверх. Возможен и другой подход — поэтапная детализация алгоритма, т.е. разделение основной задачи на более мелкие подзадачи и их дальнейшее решение. Вторая технология носит название программирование сверху вниз. Применительно к нашей задаче она заключалась бы в том, что мы сначала разработали бы алгоритмы сложения, вычитания и другие, а уже потом создали бы алгоритмы добавления и извлечения элементов.

Теперь проверим новые алгоритмы “в деле”. Задача — используя стек, получить на экране число 2009, при условии, что в стек можно помещать только числа от 1 до 9.

Один из вариантов решения представлен в таблице:

Соответствующая программа:

алг число 2009

нач

· |Подготовим стек

· Очистка

· |Начинаем работу

· Поместить(5)

· Поместить(5)

· Поместить(5)

· Поместить(4)

· Поместить(4)

· Умножить

· Умножить

· Умножить

· Умножить

· Поместить(9)

· Сложить

· |Покажем результат

· вывод Вершина

кон

Запустим программу ( + ), в окне отладки получим следующий результат: 2009 .

Литература

1. Насыров Н.А. Стек — первое знакомство. / “В мир информатики” № 129 (“Информатика” № 17/2009).