Реализация
Алгоритм Infix
Построение из инфиксной записи
Для простоты мы будем считать, что правильное арифметическое выражение подается в одной строке, без пробелов, а каждый операнд записан одной буквой. Приоритет операций определяется расставленными скобками: ими должна быть снабжена каждая операция.
Если не достигнут конец строки ввода, прочитать очередной символ.
Если этот символ - открывающая скобка, то:
- создать новую вершину дерева;
- вызвать алгоритм Infix для ее левого поддерева;
- прочитать символ операции и занести его в текущую вершину;
- вызвать алгоритм Infix для правого поддерева;
- прочитать символ закрывающей скобки (и ничего с ним не делать).
Иначе:
- создать новую вершину дерева;
- занести в нее этот символ.
Мы воспользуемся здесь описанием типа данных 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.
Для простоты предположим, что правильное арифметическое выражение подается в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, будем считать, что из записи удалены все скобки: это вполне допустимо, так как операция всегда предшествует своим операндам, следовательно, путаница в порядке выполнения невозможна.