Дано выражение а*(-b)+с/d
Операции выполняются над выражениями, представленными в виде
бинарных деревьев. Такие выражения можно символьно складывать,
ш1.0
Дерево Дерево
общего вида: ▌ бинарного вида:
(+) ▌ (+)
/ ▌ │
(*) (/) ▌ (*)─────────(/)
/ / ▌ │ │
(а) (-) (с) (d) ▌ (а)──(-) (с)──(d)
│ ▌ │
(b) ▌ (b)
Рис.6.30 Представление выражения в виде дерева
┌──┬───┬──┐
┌──────────┼─ │ + │ ─┼────────┐
│ └──┴───┴──┘ │
┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐
┌─┼─ │ * │ ─┼─┐ ┌─┼─ │ / │ ─┼─┐
│ └──┴───┴──┘ │ │ └──┴───┴──┘ │
┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐
│//│ а │//│ │//│ - │ ─┼─┐ │//│ c │//│ │//│ d │//│
└──┴───┴──┘ └──┴───┴──┘ │ └──┴───┴──┘ └──┴───┴──┘
┌──┬─┴─┬──┐
│//│ b │//│
└──┴───┴──┘
Рис. 6.31 Представление выражения в виде бинарного дерева.
перемножать, вычитать, дифференцировать, интегрировать, сравни-
вать на эквивалентность и т.д. Т.е. получаются символьные выраже-
ния, которые можно закодировать в виде таблиц:
(-) - операция унарного минуса;
() - операция возведения в степень;
(+) - операция сложения;
(*) - операция умножения;
(/) - операция деления.
(Е) - указательная переменная, адресующая корень дерева,
каждая вершина которого состоит из левого указателя (LPТR), пра-
вого указателя (RPTR) и информационного поля TYPE.
┌────┬────┬────┐
│LPTR│TYPE│RPTR│
└────┴────┴────┘
Для неконцевой вершины поле TYPE задает арифметическую опе-
рацию, связанную с этой вершиной. Значения поля TYPE вершин
+,-,*, /, (-) и равны 1, 2, 3, 4, 5, 6 соответственно.
Для концевых вершин поле символа в TYPE имеет значение 0,
что означает константу или переменную. В этом случае правый ука-
затель вершины задает адрес таблицы символов, который соответс-
твует данной константе или переменной. В дереве указывается тип
оператора, а не он сам, что позволяет упростить обработку таких
деревьев.
┌──┬───┬──┐
┌──────────┼─ │ + │ ─┼────────┐
│ └──┴───┴──┘ │
┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐
┌─┼─ │ * │ ─┼─┐ ┌─┼─ │ / │ ─┼─┐
│ └──┴───┴──┘ │ │ └──┴───┴──┘ │
┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐ ┌──┬─┴─┬──┐
│//│ а │ │ │//│ - │ ─┼─┐ │//│ c │ │ │//│ d │ │
└──┴───┴─┼┘ └──┴───┴──┘ │ └──┴───┴─┼┘ └──┴───┴─┼┘
│ ┌──┬─┴─┬──┐ │ │
│ │//│ b │ │ │ │
│ └──┴───┴─┼┘ │ │
│┌───────────────────┘ │ │
││ ┌──────────────────────────┘ │
││ │┌───────────────────────────────────────┘
││ ││ ┌─────────┬────────────┐
││ ││ │Symbol │Value │
││ ││ ├─────────┼────────────┤
││ │└──┼─ D │ │
││ │ ├─────────┼────────────┤
││ └───┼─ C │ │
││ ├─────────┼────────────┤
│└─────┼─ B │ │
│ ├─────────┼────────────┤
│ │ E │ │
│ ├─────────┼────────────┤
└──────┼─ A │ │
└─────────┴────────────┘
Рис.2.31 Таблица символов
Процедура вычислений:
Создается семимерный массив меток и его элементам задаются
требуемые значения.Оператор генерирует метку исходя из значения
поля корневой вершины. И передается управление управление опера-
тору, помеченного меткой. Если данная вершина концевая, то в ка-
честве значения выдается значение переменной или константы, обоз-
наченной этой вершиной. Эта операция выполняется путем использо-
вания правого указателя данной вершины для ссылки на нужную за-
пись в таблице символов. Для неконцевой вершины инициализируются
рекурсивные вычисления ее поддеревьев, характеризующих операнды
текущего оператора. Этот процесс продолжается до тех пор, пока не
будут достигнуты листья дерева. Для полученных листьев значения
выбираются из соответствующих записей таблицы символов.
Ниже приводится программа, вычисляющая арифметическое выра-
жение.