Графы-выражения.

(x+1)*(x+1)²+(x+1)*x

Дерево хранит многократно каждое вхождение, но не собственно выражение.

Ациклический граф.

Такие графы соответствуют выражениям

частичного порядка.

Задача вычисления выражения, представленного графом, аналогична случаю дерева.

Подзадача «поиск атома, значения атома» аналогична. Но уничтожить терм теперь можно лишь в случае, когда на него нет других ссылок.

1 способ – хранить обратные ссылки и, в случае удаления, проверять, присутствуют ли они.

2 способ – хранить в каждой вершине счётчик ссылок на эту вершину. При каждом вычислении уменьшать значение счётчика. В случае равенства нулю – удалять вершину.

Упражнение. Завершить задачу о вычислении выражения.

* Преобразовать выражение из представления деревом в представление графом и обратно.

Раздельное описание абстрактных типов.