Много времени прошло со времени начального поста. Снова занялся той идеей.
И сформулировал требования к структуре данных, которую хочу реализовать:
1. Выражение должно представляться в виде дерева, но не бинарного. Например, если складываются несколько переменных, то должна быть одна вершина "сложение" и список переменных, которые складываются.
2. При печати дерева, выражение должно печататься в том же виде, как оно было введено пользователем. А внутри дерево может быть организовано, как будет удобнее.
3. Определение одинаковых подвыражений должно быть очень дешево.
4. Должна сохраняться версионность изменений, чтобы можно было посмотреть как выражение выглядело на каждом этапе.