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

Реализация

Алгоритм Infix

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

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

Если не достигнут конец строки ввода, прочитать очередной символ.

Если этот символ - открывающая скобка, то:

1. создать новую вершину дерева;
2. вызвать алгоритм Infix для ее левого поддерева;
3. прочитать символ операции и занести его в текущую вершину;
4. вызвать алгоритм Infix для правого поддерева;
5. прочитать символ закрывающей скобки (и ничего с ним не делать).

Иначе:

1. создать новую вершину дерева;
2. занести в нее этот символ.

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

procedure infix(var p: ukaz);var c: char;begin read(c); if c = '(' then begin new(p); infix(p^.left); read(p^.symbol); {'+', '-', '*', '/'} infix(p^.right); read(c); {')'} end else begin {'a'..'z','A'..'Z'} new(p); p^.symbol:= c; p^.right:= nil; p^.left:= nil end;end; begin ... infix(root); ...end.

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