2014-02-24
778
Рис.. Дерево выражений
Рис. 73. Дерево выражений
Различные алгоритмы обхода дерева выражений соответствуют различной структуре представления выражения в виде строки.
Нисходящему обходу соответствует префиксная форма представления, т. к. в ней знак операции предшествует операнду:
* + А 10. / B 5.2.
Восходящему обходу соответствует постфиксная форма представления, т. к. в ней знак операции находится после операндов:
A 10. + B 5.2 / *.
Смешанному обходу соответствует инфиксная форма представления, т. к. в ней знак операции находится между операндами:
А + 10. * В / 5.2.
Для того чтобы задать приоритеты операций, используется абсолютно скобочная форма, в которой каждое подвыражение заключается в круглые скобки:
((A + 10.) * (B / 5.2)).
На рис. 74 приведено дерево, смешанный обход которого позволяет получить бесскобочную инфиксную форму, эквивалентную дереву рис. 73, а скобочная инфиксная форма задает совсем другие приоритеты операций. Заметим, что подобная проблема не может возникнуть при использовании префиксной или постфиксной формы представления выражения.
(А + (10. * (В / 5.2)))
Какой алгоритм обхода необходимо использовать для того, чтобы подсчитать значение арифметического выражения, представленного в виде дерева?
