Tree-based math expressions using func delegate objects

Question

I want to implement a general tree data structure in C # that has a Tree<E> class that references a root TreeNode<E> object that contains a linked list of children and one parent of the same node type. This is a basic tree structure, and I have no problem implementing this part.

I want to expand this tree structure by creating a Function that extends Tree<double> along with its addition of node type Expression , which extends TreeNode<double> accordingly. I want to use this structure to represent mathematical functions that can be evaluated using appropriate variables.

I am now at the design stage of this project, so there are many ways to implement this, but I am looking for a design that has an appropriate level of abstraction to cover all types of functions, while keeping their parameter signatures tight. For example, I should be able to create Function during the execution of mathematical functions:

f() = 42 , f(x) = x^2 , f(x, y) = x/y + 5 , etc.

If each Expression has its own list of children (subexpressions that are broken down to determine the function process based on its arguments), then Expression should use some kind of evaluation method that takes double values ​​and splashes out their scalar values ​​(or, if possible, extracts them to the Vector level).

I'm not too experienced with functional languages ​​like LINQ, but if anyone is there, will there be an easy and powerful way to implement what I plan to use? It would be great if I did not have to create specific classes for each basic operation (for example, SinExpression(X) or AdditionExpression(X,Y) ), but instead one could define mathematical functions on the fly, which could potentially be stored in the Dictionary, provided that all variables are either different expressions or are reduced to floating point values. At this point, concrete function classes could extend these abstract ones if I just needed to define an evaluation function in the base constructor.

I also want to note that it is important to maintain a tree structure, because I plan to use these expressions in a separate program that will directly modify the tree of function expressions (changing nodes, deleting branches, etc.).

Can someone point me in the right direction? I would be very grateful.

Answer 1

An API already exists that presents complex operations as node trees; LINQ Expression API. For a trivial example, you can force the compiler to build trees for you - for example:

 Expression<Func<double,double,double>> f = (x,y) => Math.Sin(x/y) + 5; 

This can be used to evaluate things by calling Compile() , i.e.

 var func = f.Compile(); // this is a Func<double,double,double> Console.WriteLine(func(12,5)); Console.WriteLine(func(23,4)); 

But the expression tree is more complex and can be arbitrarily checked. Alternatively, you can use ExpressionVisitor to share fragments. For example, suppose we want to replace “x” with “ln (x)” as part of a random genetic mutation:

 // swap x for ln(x) var munged = SwapExpressionVisitor.Swap( f, // the lambda to rewrite f.Parameters[0], // "x" Expression.Call(typeof(Math), "Log", null, f.Parameters[0]) // ln(x) ); // (x, y) => (Sin((Log(x) / y)) + 5) func = munged.Compile(); Console.WriteLine(func(12, 5)); Console.WriteLine(func(23, 4)); 

using a utility like:

 class SwapExpressionVisitor : ExpressionVisitor { public static Expression<T> Swap<T>(Expression<T> lambda, Expression from, Expression to) { return Expression.Lambda<T>( Swap(lambda.Body, from, to), lambda.Parameters); } public static Expression Swap( Expression body, Expression from, Expression to) { return new SwapExpressionVisitor(from, to).Visit(body); } private readonly Expression from, to; public SwapExpressionVisitor(Expression from, Expression to) { this.from = from; this.to = to; } public override Expression Visit(Expression node) { return node == from ? to : base.Visit(node); } }