Стек и компьютер

vmi@1september.ru

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

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

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

— Очистка — проводит заполнение стека-массива нулями;

— Вершина — функция, возвращающая число на вершине стека (само число из стека не извлекается), а также 4 алгоритма, осуществляющие арифметические операции над двумя числами, находящимися в стеке.

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

алг Пример

нач цел n

n := (3 + 5) * 2

кон

Для нас пример окажется простым, нужно всего лишь результат сложения двух чисел умножить на 2. Так же поступит и компьютер. Если вдруг в примере мы уберем скобки, то компьютер сначала умножит два числа, а уже потом выполнит сложение, т.е. поступит по всем правилам математики. Зададим вопрос — как он это делает? Ведь при сложных выражениях, с большим количеством операций, скобок и т.п., задача существенно усложняется, но тем не менее компьютер с ней успешно справится!

Дело в том, что на самом деле в компьютере каждое действие проводится над двумя числами, которые находятся в одном и том же месте, результат также помещается в одно и то же место и затем участвует в следующем действии, выполняемом по тем же правилам¹. Вам это ничего не напоминает? Да, конечно, так выполняются действия во вспомогательных алгоритмах Сложить , Вычесть , Умножить и Разделить , описанных в [2] (напомним, что в них действия выполняются над двумя числами, находящимися в двух “верхних” элементах стека, а результат размещается на его вершине). То есть в компьютере некоторый участок оперативной памяти организован в виде стека, и при вычислениях используются только числа на его вершине и в элементе, расположенном рядом с вершиной. Но для применения такой схемы вычислений необходимо преобразовать рассчитываемое выражение в специальную форму. Эта форма называется “постфиксной нотацией”, а привычная нам форма записи выражений в виде “3 + 4” и “7 / 9” — “инфиксной нотацией”. В последней знак операции (в данном случае это “+” и “/”) записывается между опе­рандами (числами, над которыми выполняются действия), а при постфиксной нотации — знак указывается после опе­рандов (в ней приведенные выражения будут выглядеть, соответственно, как “3 4 +” и “7 9 /”).

Как, очевидно, известно читателям, переводом программы, написанной нами на языке программирования высокого уровня, на машинный язык занимается специальная программа — транслятор. Так вот, при расчетах значений инфиксных выражений транслятор сначала переводит их в постфиксную форму, а затем вычисляет значение постфиксного варианта выражения по описанным только что правилам. Каждый из этих двух алгоритмов тре­бует всего одного прохода по выражению слева направо. Обоим алгоритмам и требуется “компьютерный стек” для выполнения операций, но стек в этих алгоритмах используется для разных целей.

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

Сначала приведем вариант, при котором в исходном инфиксном выражении скобки отсутствуют. Здесь правила такие.

1. Просматривать инфиксную запись посимвольно слева направо.

если текущий символ — операнд (число),

то

добавить его в постфиксную запись

все

если текущий символ — знак операции,

то

если стек пуст,

то

поместить этот знак в стек

иначе

если приоритет текущей операции >

приоритета операции на вершине

стека,

то

поместить текущий знак операции

в стек

иначе

Записывать знаки операций

из стека в постфиксную запись,

пока приоритет операции

на вершине стека >= приоритету

текущей операции (знаки из стека

извлекаются).

Поместить текущий знак операции

в стек.

все

все

все

2. Добавлять знаки операций из стека в постфиксную запись, пока стек не пуст.

Потренируемся на бумаге.

Пример 1. Инфиксное выражение: 5+2*3+6.

Этапы формирования соответствующего постфиксного выражения приведены в таблице:

Как транслятор проводит вычисления согласно постфиксному выражению, мы расскажем в следующей части статьи.

Когда в исходном инфиксном выражении скобки имеются, правила формирования постфиксного выражения такие [3]³.

1. Ввести в стек левую скобку “(”.

2. Добавить правую скобку “)” в конец исходного (инфиксного) выражения (фактически мы заключили исходное выражение в скобки).

3. Пока стек не пуст, просматривать инфиксную запись слева направо и выполнять следующие действия:

1) если текущий символ — операнд (число), то добавить его в новое (постфиксное) выражение;

2) если текущий символ — левая скобка, то поместить ее в стек;

3) если текущий символ — знак операции, извлекать знаки операций из стека (если они там есть), пока соответствующие им операции имеют равный или более высокий приоритет по сравнению с текущей операцией, и вставлять извлеченные знаки операций в новое выражение. Вставить текущий символ — знак операции в стек;

4) если текущий символ — правая скобка, то извлекать знаки операций из стека и вставлять их в новое выражение до тех пор, пока на вершине стека не появится левая скобка. Извлечь из стека левую скобку и отбросить ее.

Также потренируемся на бумаге.

Пример 2. Напишем в постфиксной форме выражение (3 + 5) * 2.

Шаг 0. Вводим в стек левую скобку “(”. Добавляем правую скобку “)” в конец исходного выражения:

— состояние стека⁴:

— инфиксное выражение: (3 + 5) * 2)

Шаг 1. Текущий символ — левая скобка. Согласно правилам помещаем ее в стеке:

— состояние стека:

Шаг 2. Текущий символ — число 3. Добавляем эту цифру в новое выражение:

— состояние стека:

— постфиксное выражение: 3

Шаг 3. Текущий символ — “+”. По правилам мы должны извлечь из стека все знаки операций, имеющие равный или более высокий приоритет, но в стеке знаков нет, поэтому просто размещаем символ “+” в стеке:

- состояние стека:

— постфиксное выражение: 3

Шаг 4. Текущий символ — число 5. Добавляем его в постфиксное выражение:

— состояние стека:

— постфиксное выражение: 35

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

— состояние стека:

— постфиксное выражение: 35+

Шаг 6. Текущий символ — “*”. Поскольку в стеке знаков операций нет, то вставляем в него текущий символ:

— состояние стека:

— постфиксное выражение: 35+

Шаг 7. Текущий символ — число 2. Приписываем его:

— состояние стека:

— постфиксное выражение: 35+2

Шаг 8. Текущий символ – правая скобка. По правилам извлекаем все знаки операций и добавляем их в постфиксное выражение, пока не встретим левую скобку (в нашем случае добавляется знак “*”). Также извлечем из стека левую скобку:

— состояние стека:

— постфиксное выражение: 35+2*

Итак, окончательно получим: 35+2* (еще раз напомним, что в качестве операндов мы рассматриваем только положительные однозначные числа).

Задания для самостоятельной работы

Преобразуйте следующие выражения в постфиксную форму:

а) 5+6/3;

б) 9/3+5*2;

в) (6+2)*5–8/4.

Литература

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

2. Насыров Н.А. Учим стек вычислять. / “В мир информатики” № 130 (“Информатика” № 18/2009).

3. Дейтел Харви, Дейтел Пол. Как программировать на С++. М.: Бином, 2006.

---

¹ Согласитесь, что такая схема вычислений гораздо проще сложных правил учета скобок, приоритета операций и т.п.

²Имеются и другие алгоритмы решения этой задачи

³Вершина стека - крайний слева элемент