2

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?

Community
  • 1
  • 1
Koronis
  • 49
  • 5
  • why does the right side imply b!=c? does (distinct a b) == b? It is unclear to me what your operator "returns" is that a true/false, or a distinct set? Anyways, would that not depend on the operator on a case by case basis how you have to transform it? – MBoros Oct 25 '15 at 09:58
  • Hi @MBoros, the operator returns true, if it's operands are pairwise distinct. Transforming (distinct (distinct a b) c) to infix notation it gets `a distinct b distinct c`, which is the same as `a != b != c`. I hope that clarifies it. – Koronis Oct 25 '15 at 13:20
  • I was thinking about introducing a new binary operator $ that actually doesn't do anything. But in the end I need to transform the tree back into a valid string and I don't know how to remove the brackets and $ consistently then. To clarify: `(distinct a b c)` could be represented as `(distinct ($ ($ a b) c))` – Koronis Oct 25 '15 at 13:26

1 Answers1

1

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.

MBoros
  • 1,090
  • 7
  • 19