16.6 Алгоритм вычисления составляющих выражения, состоящих из констант

В процессе преобразования арифметических выражений может накопиться несколько констант. Например, 10 + 2.5 + 3 * 6/x. Поэтому необходимо произвести вспомогательные вычисления для констант данного выражения. На рис.15.4 показан пример преобразования синтаксического дерева при дополнительном вычислении констант.

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

       1. Узел <D> вычислим, если его сын является константой или узел <E>, стоящий в скобках, также вычислим.
       2. Узел <T> вычислим, если все его сыновья вычислимы.
       3. Узел <E> вычислим, если все его сыновья вычислимы.
       Пример свертывания узлов показан на рис.15.5


рис.155 Пример свертывания узлов

       Тогда можно определить следующий рекурсивный алгоритм:
       1. Если <D> вычислим, вернуть значение.
       2. Если при рассмотрении соседних сыновей узла <T> они окажутся вычислимы, то свернуть и продолжить попарное сравнение.
       3. Если все сыновья <T> вычислимы, вернуть значение.
       4. Если при рассмотрении соседних сыновей узла <E> они окажутся вычислимы, то свернуть и продолжить попарное сравнение.
       Необходимо сделать замечание, что данный алгоритм работает только при отсортированном синтаксическом дереве (см. алгоритм лексикографического упорядочения), у которого константы стоят рядом.