Реферат Курсовая Конспект
МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ. - раздел Образование, Графы Дано Выражение А*(-B)+С/d Операции Выполняются Над Выражениями, Пред...
|
Дано выражение а*(-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 Таблица символов
Процедура вычислений:
Создается семимерный массив меток и его элементам задаются
требуемые значения.Оператор генерирует метку исходя из значения
поля корневой вершины. И передается управление управление опера-
тору, помеченного меткой. Если данная вершина концевая, то в ка-
честве значения выдается значение переменной или константы, обоз-
наченной этой вершиной. Эта операция выполняется путем использо-
вания правого указателя данной вершины для ссылки на нужную за-
пись в таблице символов. Для неконцевой вершины инициализируются
рекурсивные вычисления ее поддеревьев, характеризующих операнды
текущего оператора. Этот процесс продолжается до тех пор, пока не
будут достигнуты листья дерева. Для полученных листьев значения
выбираются из соответствующих записей таблицы символов.
Ниже приводится программа, вычисляющая арифметическое выра-
жение.
– Конец работы –
Эта тема принадлежит разделу:
Графы Логическая структура определения структура отображающая... Основные операции над деревьями... Над деревьями определены следующие основные операции для...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов