CODEWITHSUNDEEP
constraintsexpression-treespolish-notation
Koronis
Koronis

Reputation: 49

Chainable/N-ary operations support in Prefix/Polish Notation Trees

Prefix Notation conversion into a tree is usually done like this:

Create a binary tree from an algebraic expression

However, I need to support so called chainable operations that have more than two operands. If that operation is splittable i.e

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

there is no problem. 

     +
   /   \
  +     c
 / \
a   b

However if an operator is not splittable this does not work. One example is the pairwise distinct operator.

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

the left side implies a != b, a != c and b != c, while the right side implies only a != b and b != c. Trying to build an n-ary tree would probably lead to not being able to traverse the tree very well:

distinct
 / | \
a  b  c

Does somebody have experience with this kind of problem and has an idea on how to solve the issue?

Upvotes: 2

Views: 77

Answers (1)

MBoros
MBoros

Reputation: 1140

The c# System.Linq.Expressions namespace solves it by having a big range of node types, and a base class visitor, where you can override the visit method of each node type, by default just traversing the whole tree. For example there is a node type for calling a method, where the method definition, the object, and all arguments are all children of the MethodCallExpression node, and the return value is what the node represents. You can see it is not a binary tree, not even anything regular.

Upvotes: 1

Related Questions