Закрепление материала: Выражения

Модуль "Выражения" • урок 6 из 7 • ~7 минут

Суть урока. Краткое резюме модуля. Выражение естественно представимо двоичным деревом: листья - операнды, узлы - операции, приоритет задан глубиной. Три обхода дерева дают три формы записи, а стековые алгоритмы (Рутисхаузера, Бауэра-Замельзона, Дейкстры) переводят привычную инфиксную запись в ОПЗ, которая вычисляется на стеке за один проход.
Выражения: дерево выражения 2 + 3 * 4 и три формы записи - префиксная, инфиксная и постфиксная (ОПЗ)
Главная картина модуля: одно дерево - три формы записи

Коротко: главное

  • Дерево выражения - двоичное: листья содержат операнды, внутренние узлы - операции. Приоритет задан структурой: что глубже - вычисляется раньше, скобки не нужны.
  • Три формы записи = три обхода дерева: КЛП дает префиксную (польскую), ЛКП - инфиксную (нужны скобки), ЛПК - постфиксную, она же обратная польская запись (ОПЗ).
  • ОПЗ вычисляется на стеке за один проход: операнд - в стек, операция - снять два верхних, вычислить, вернуть результат. Ни скобки, ни приоритеты не нужны.
  • Эволюция алгоритмов разбора: Рутисхаузер (уровни вложенности, только полная скобочная структура) → Бауэр-Замельзон (два стека и таблица переходов, учитывает приоритет) → Дейкстра (стек операторов и выходная очередь - классика, "сортировочная станция").

Три алгоритма разбора рядом

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

Алгоритм Рутисхаузера (1951)

Каждой лексеме присваивается уровень вложенности; тройка "операнд - операция - операнд" на максимальном уровне сворачивается во вспомогательную переменную R, и так до одной переменной.

Алгоритм Бауэра-Замельзона (1959)

Первый стековый транслятор: действие на каждом шаге выбирается по таблице переходов от пары "вершина стека операций + текущая лексема", операнды и результаты живут во втором стеке.

Алгоритм Дейкстры (1961)

"Сортировочная станция": операнды сразу едут в выход, операции - в стек-тупик, а новая операция выталкивает из стека все, что не слабее ее. На выходе получается готовая ОПЗ.

Чтобы уложить модуль в голове, по каждому алгоритму достаточно помнить крючок-образ, плюсы и минусы:

1951
Рутисхаузера
"уровни и тройки"
  • не нужны ни стек, ни рекурсия
  • правила предельно простые
  • только полная скобочная структура
  • несколько проходов по строке
1959
Бауэра-Замельзона
"два стека и таблица"
  • один проход, счет по ходу разбора
  • понимает приоритет и неполные скобки
  • нужна таблица переходов
  • самое сложное устройство из трех
1961
Дейкстры
"вагоны прямо, локомотивы в тупик"
  • один стек и простые правила
  • классика, живет в компиляторах до сих пор
  • выдает ОПЗ, вычислять ее - отдельный проход

Вычисление ОПЗ на стеке - опорный пример

Один и тот же пример проходит через весь модуль: дерево 2 + 3 * 4 дает ОПЗ 2 3 4 * +, а стек вычисляет ее за один проход:

ОПЗ:  2 3 4 * +
  2  ->  [2]
  3  ->  [2 3]
  4  ->  [2 3 4]
  *  ->  снять 3 и 4, вычислить 12  ->  [2 12]
  +  ->  снять 2 и 12, вычислить 14 ->  [14]
ответ = 14

Проверьте себя

Вопрос 1

Что находится в листьях дерева выражения?

Вопрос 2

Какая форма записи вычисляется за один проход без скобок и без знания приоритетов?

Вопрос 3

Какое главное ограничение у алгоритма Рутисхаузера?

Вопрос 4

Какие структуры данных использует алгоритм Бауэра-Замельзона?

Вопрос 5

В алгоритме Дейкстры встретилась закрывающая скобка. Что происходит?

Вопрос 6

Чему равно значение ОПЗ 2 3 4 * +?

Как вам урок? Спасибо за отзыв!