Здравствуйте, maggot, Вы писали:

M>

M>a + b + c

M>  +       или     +       или     +
M> / \             / \             / \
M>a   +           +   c           +   b
M>   / \         / \             / \
M>  b   c       a   b           a   c
M>

M>a, b, c — вообще говоря выражения, а не переменные

M>Мне нужно сравнить выражение с шаблоном.
M>Шаблон:
M>

M>a + c
M>представлено деревом так
M>  +
M> / \
M>a   c
M>

Что значит сравнить выражение с шаблоном ? Шаблон должен содержаться как поддерево в дереве с учетом возможных преобразований деревьев ?

Если я тебя правильно понял, то вот мои соображения по теме.

Все зависит от того какие операции могут встречаться в твоем выражении и от их свойств. Если только сложение, то поскольку действует коммутативные и ассоциативные свойства решение элементарно -- просто представляем исходное выражение не в виде дерева, а в некой канонической форме, в виде списка слагаемых. Как-то так -- SUM(a,b,c). Твой шаблон будет чем-то в вроде SUM(a,c). В итоге надо просто отыскать элементы второго списка слагаемых в первом.

Если имеются более сложные комбинации операций, то тут тоже можно попробовать отыскать каноническую форму исходных выражений. На самом деле вопросами поиска такой канонической формы занимается раздел computer sciense, кототрый называют переписыванием формул (переписыванием термов, term rewriting). Правда, классическая задача переписывания формул несколько отличается от твоей. В классической задаче даны два выражения и набор эквационных спецификациях, характеризующие свойства операций. Например

a + b = b + a
a + (b+c) = (a+b)+c
a* 1 = a
a* 0 = 0
a + 0 = a
...
и т.д.

Необходимо проверить равенство двух исходных выражений с учетом свойств операций. Проверяется равенство путем приведения этих выражений к канонической форме и сравнению канонических форм. Вид канонической формы (и вообще ее наличие, т.н. свойство Черча-Россера) зависит от набора эквационных спецификаций.

Но в целом задача близка к твоей. Можешь поковырять в эту сторону. Ищи в гугле "переписывание формул", "переписывание термов", "term rewriting". Есть кое-что по теме в книге про графы. Кстати, если что-нибудь полезное найдешь, скажи мне.