Мы покажем механизм стековой арифметики на простых примерах. Но сначала стоит, видимо, вспомнить некоторые понятия математики.

Вы, конечно, помните, что арифметическое выражение состоит из операндов (чисел), знаков операций '+', '-', '*', '/' и скобок, определяющих последовательность выполнения действий. При отсутствии скобок эта последовательность определяется стандартными соглашениями о приоритете операций.

Однако задавать последовательность действий можно и без скобок, - существуют бесскобочные линейные формы записи арифметических выражений. Идея таких записей будет достаточно ясна, если сначала "уточнить" первую, - скобочную, - запись. С этой целью добавим в формуле лишние скобки, которые избавят нас от учета стандартных соглашений. Получим то же выражение в расширенной скобочной форме:

((4*(6-3))+((8-6)/2)))

А теперь начнем изменять запись этого выражения. Прежде всего, внешнее действие (A+B) запишем, снимая его скобки, в виде

+ A B

или, для нашего, примера

+ (4* (6-3)) ((8-6)/2)

Аналогично преобразуем аргумент A

+ * 4 (6-3) ((8-6)/2)

А дальше будем преобразовывать каждую следующую скобку, двигаясь от внешних скобок к внутренним:

+ * 4 - 6 3 ((8-6)/2)

+ * 4 - 6 3 / (8-6) 2

+ *4 - 6 3 / - 8 6 2

Получившаяся форма называется префиксной записью (действие пишется перед операндами) или польской записью, так как ее появление связывается с именем польского математика Яна Лукасевича (Jan Łukasiewicz, 1878-1956)

Выражение, записанное в префиксной записи, вычисляется так: читается первый элемент записи, если это число, то оно является результатом, если же это знак действия, то из остатка записи берутся два числа (аналогичным образом), и с ними производится нужное действие. Итак,

result(+ * 4 - 6 3 / - 8 6 2)= A1 + B1,

где A1 и B1 нужно еще вычислить из записи

* 4 - 6 3 / - 8 6 2

Имеем

result(* 4 - 6 3 / - 8 6 2) = A2 * B2.

Опять таки, A2 = 4, а В2 вычисляется из оставшейся записи

result(- 6 3 / - 8 6 2) = A3 - B3

Тут уже просто: A3=6, B3=3, так что B2 = 3, и мы нашли A1=3*4=12. Настала очередь операнда B1, который находится по остатку записи.

result(/ - 8 6 2) = A4 / B4

и так далее.

Наряду с префиксной используется и постфиксная, или обратная польская запись, которая еще более популярна. В ней наш пример записывается так:

4 6 3 - * 8 6 - 2 / +

Обратная польская запись очень удобна для стека, если предположить, что запись поступает в стек поэлементно и каждое поступившее число просто заталкивается в стек, а каждая операция снимает со стека два числа, выполняет с ними свое действие и кладет в стек результат. Все можно записать такой таблицей

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