Алгоритм Postfix

Построение из постфиксной записи

Реализация

Алгоритм Prefix

  1. Если не достигнут конец строки ввода, прочитать очередной символ.
  2. Создать новую вершину дерева, записать в нее этот символ.
  3. Если символ - операция, то:
    1. вызвать алгоритм Prefix для левого поддерева;
    2. вызвать алгоритм Prefix для правого поддерева.

Вновь воспользуемся описанием типа данных ukaz, приведенным на рис. 12.1:

procedure prefix(var p: ukaz);begin new(p); read(p^.symbol); if p^.symbol in ['+','-','*','/'] then begin prefix(p^.left); prefix(p^.right); end else begin p^.left:= nil; p^.right:= nil; endend; begin ... prefix(root); ...end.

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

  1. Если не достигнут конец строки ввода, прочитать очередной символ,если этот символ - операнд, то занести его в стек2),иначе (символ - операция):
    1. создать новый элемент, записать в него эту операцию;
    2. достать из стека два верхних (последних) элемента, присоединить их в качестве левого и правого операндов в новый элемент;
    3. занести полученный "треугольник" в стек.

По окончании работы этого алгоритма в стеке будет содержаться ровно один элемент - указатель на корень построенного дерева.