Алгоритм 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. Если не достигнут конец строки ввода, прочитать очередной символ,если этот символ - операнд, то занести его в стек²⁾,иначе (символ - операция):
1. создать новый элемент, записать в него эту операцию;
2. достать из стека два верхних (последних) элемента, присоединить их в качестве левого и правого операндов в новый элемент;
3. занести полученный "треугольник" в стек.

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

Дата добавления: 2014-01-03