Деревья при работе с арифметическими выражениями
Операция объединения двух символов в один использует структуру бинарного дерева. Каждый узел содержит символ и частоту вхождения. Код любого символа может быть определен просмотром дерева снизу вверх, начиная с листа. Каждый раз при прохождении узла приписываем слева к коду 0, если поднимаемся по левой ветви и 1, если поднимаемся по правой ветви. Как только дерево построено код любого символа алфавита может быть определен просмотром дерева снизу вверх, начиная с места, представляющего этот символ. Начальное значение кода пустая строка. Каждый раз, когда мы поднимаемся по левой ветви, к коду слева приписывается ноль, если справа - 1. Часть info узла дерева содержит частоту появления символа представляемого этим узлом. Дерево Хаффмена строго бинарное. Если в алфавите п символов, то дерево Хаффмена может быть представлено массивом узлов размером 2п-1. Поскольку размер памяти, требуемой под дерево известен, она может быть выделена заранее.
МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.
Дано выражение а*(-b)+с/d
Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать,
Рис.6.31 Представление выражения в виде дерева
Рис. 6.32 Представление выражения в виде бинарного дерева.
перемножать, вычитать, дифференцировать, интегрировать, сравнивать на эквивалентность и т.д. Т.е. получаются символьные выражения, которые можно закодировать в виде таблиц:
- (-) - операция унарного минуса;
- () - операция возведения в степень;
- (+) - операция сложения;
- (*) - операция умножения;
- (/) - операция деления.
- (Е) - указательная переменная, адресующая корень дерева, каждая вершина которого состоит из левого указателя (LPТR), правого указателя (RPTR) и информационного поля TYPE.
| LPTR | DATA | RPTR |
Для неконцевой вершины поле TYPE задает арифметическую операцию, связанную с этой вершиной. Значения поля TYPE вершин +,-,*, /, (-) и равны 1, 2, 3, 4, 5, 6 соответственно.
Для концевых вершин поле символа в TYPE имеет значение 0, что означает константу или переменную.
В этом случае правый указатель вершины задает адрес таблицы символов, который соответствует данной константе или переменной. В дереве указывается тип оператора, а не он сам, что позволяет упростить обработку таких деревьев.
Рис.6.33 Таблица символов
Процедура вычислений:
Создается семимерный массив меток и его элементам задаются требуемые значения.Оператор генерирует метку исходя из значения поля корневой вершины. И передается управление управление оператору, помеченного меткой. Если данная вершина концевая, то в качестве значения выдается значение переменной или константы, обозначенной этой вершиной. Эта операция выполняется путем использования правого указателя данной вершины для ссылки на нужную запись в таблице символов. Для неконцевой вершины инициализируются рекурсивные вычисления ее поддеревьев, характеризующих операнды текущего оператора. Этот процесс продолжается до тех пор, пока не будут достигнуты листья дерева. Для полученных листьев значения выбираются из соответствующих записей таблицы символов.
Ниже приводится программа, вычисляющая арифметическое выражение.