Деревья выражений

Дерево выражений – бинарное дерево, в корневых узлах которого хранятся признаки операций, а в терминальных узлах – операнды выражения (переменные или константы). Дерево выражений представлено на рис. 73.

Рис. 73. Дерево выражений

Различные алгоритмы обхода дерева выражений соответствуют различной структуре представления выражения в виде строки.

Нисходящему обходу соответствует префиксная форма представления, т. к. в ней знак операции предшествует операнду:

* + А 10. / B 5.2.

Восходящему обходу соответствует постфиксная форма представления, т. к. в ней знак операции находится после операндов:

A 10. + B 5.2 / *.

Смешанному обходу соответствует инфиксная форма представления, т. к. в ней знак операции находится между операндами:

А + 10. * В / 5.2.

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

((A + 10.) * (B / 5.2)).

На рис. 74 приведено дерево, смешанный обход которого позволяет получить бесскобочную инфиксную форму, эквивалентную дереву рис. 73, а скобочная инфиксная форма задает совсем другие приоритеты операций. Заметим, что подобная проблема не может возникнуть при использовании префиксной или постфиксной формы представления выражения.

(А + (10. * (В / 5.2)))

Рис.. Дерево выражений

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