Поддержка цепочек /N-арных операций в деревьях префиксов / польских обозначений

Question

Преобразование префикса в дерево обычно делается так:

Создать двоичное дерево из алгебраического выражения

Однако мне нужно поддерживать так называемые цепочечные операции, которые имеют более двух операндов. Если эта операция разделяемая, т.е.

(+ a b c) = (+(+ a b) c)

нет проблем.

     +
   /   \
  +     c
 / \
a   b

Однако, если оператор не разделяемый, это не работает. Одним из примеров является попарно отличный оператор.

(distinct a b c) != (distinct (distinct a b) c)

левая сторона подразумевает a!= b, a!= c и b!= c, в то время как правая сторона подразумевает только a! = b и b!= c. Попытка построить n-арное дерево, вероятно, приведет к невозможности очень хорошо пройти по дереву:

distinct
 / | \
a  b  c

Есть ли у кого-то опыт работы с такой проблемой и есть идеи, как ее решить?

Answer 1

Пространство имен C# System.Linq.Expressions решает его, имея большой диапазон типов узлов и посетителя базового класса, где вы можете переопределить метод посещения каждого типа узла, по умолчанию просто обходя все дерево. Например, существует тип узла для вызова метода, где определение метода, объект и все аргументы являются дочерними по отношению к узлу MethodCallExpression, а возвращаемое значение - это то, что представляет узел. Вы можете видеть, что это не двоичное дерево, и даже не что-то регулярное.