Стек. Логическое описание: рекурсия и обратная польская запись

Модуль "Стек" • урок 2 из 8 • ~8 минут

Стек. Логическое описание: рекурсивная структура

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

Получается рекурсивное определение:

СТЕК = ( ВЕРШИНА + ТЕЛО_СТЕКА ) | ПУСТОЙ_СТЕК

База этой рекурсии - пустой стек. Такое определение не просто красиво: оно объясняет, почему стек и рекурсия так естественно дружат, и лежит в основе целого класса вычислительных машин.

Стековая модель вычислений

На рекурсивном взгляде на стек построена стековая модель вычислений. В ней работают язык Forth, виртуальная машина Java (JVM) и механизм вызова функций практически во всех современных процессорах. Идея: программе не нужны именованные переменные для промежуточных результатов - все живет в стеке.

Обратная польская запись

Привычная нам запись выражений - инфиксная: 1 + 2 * 3. Чтобы ее понять, нужны скобки и правила приоритета операций. Стек позволяет избавиться и от того, и от другого: в постфиксной записи (она же обратная польская, ОПЗ) операция пишется после своих операндов.

Выражение (1 + 2) * 4 в ОПЗ выглядит так: 1 2 + 4 *. Никаких скобок - порядок вычислений однозначно задан самой записью.

Как вычислить выражение в ОПЗ

1. Читаем выражение слева направо.
2. Встретили операнд (число) - кладем его в стек (Push).
3. Встретили операцию - снимаем (Pop) со стека два верхних числа, выполняем операцию и кладем результат обратно (Push).
4. Когда выражение кончилось, в стеке лежит ровно одно число - ответ.

Проследим на примере 1 2 + 4 *: в стек попадают 1 и 2; операция + снимает их и кладет 3; затем в стек попадает 4; операция * снимает 4 и 3 и кладет 12. Выражение кончилось, в стеке одно число - ответ 12.

Кусочек стековой машины на C

Так выглядит операция сложения в постфиксном калькуляторе. Функция не принимает аргументов-чисел: она берет их со стека и туда же возвращает результат:

#include <stdio.h>
/* Функции Push, Pop и тип Stack - из урока 1 */

void ExecuteAdd(Stack* s) {
    /* 1. Снимаем два верхних операнда */
    int b = Pop(s); /* второе слагаемое: оно было на самом верху */
    int a = Pop(s); /* первое слагаемое */

    /* 2. Выполняем операцию */
    int result = a + b;

    /* 3. Кладем результат обратно в стек */
    Push(s, result);
}

Для вычитания и деления порядок операндов важен: верхним в стеке лежит второй операнд. Именно поэтому в коде выше сначала снимается b, потом a.