4

我想在 C# 中实现一个通用树数据结构，它有一个类Tree<E>，它引用一个根TreeNode<E>对象，该对象包含一个子节点的链接列表和相同节点类型的单个父节点。这是一个基本的树形结构，实现这部分我真的没有任何问题。

我想扩展这个树结构来创建Function，它扩展Tree<double>，以及它的补充节点类型Expression，它适当地扩展TreeNode<double>。我想用这个结构来表示可以用函数的适当变量评估的数学函数。

我目前处于该项目的设计阶段，因此有很多方法可以实现它，但我正在寻找具有适当抽象级别的设计，以涵盖所有类型的功能，同时仍保持其参数签名的密封. 例如，我应该能够Function在运行时为数学函数创建一个：

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

如果每个Expression人都有自己的子项列表（分解以定义给定参数的函数过程的子表达式），那么Expression应该使用某种评估方法，它接受double值并吐出它们的标量值（或者如果可能，将其提取到向量级别）。

我对 LINQ 之类的函数式语言不太熟悉，但如果有人是的话，是否有一种简单而强大的方法来实现我计划使用的功能？如果我不必为每种基本操作（比如SinExpression(X)或AdditionExpression(X,Y)那些）创建具体的类，而是能够动态定义可能存储在字典中的数学函数，那就太好了，前提是所有变量要么是其他表达式，要么归结为浮点值。那时，如果我需要的话，具体的函数类可以扩展这些抽象的类，只需在基本构造函数中定义评估函数即可。

我还想指出，维护树结构很重要，因为我计划在一个单独的程序中使用这些表达式，该程序将直接更改函数的表达式树（更改节点、删除分支等）。

谁能指出我正确的方向？我将不胜感激。

4

1 回答 1

5

已经有一个 API 可以将复杂的操作表示为节点树；LINQ ExpressionAPI。对于一个简单的示例，您可以让编译器为您构建树 - 例如：

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

这可以通过调用来评估Compile()事物，即

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

但是表达式树比较复杂，可以任意检查。此外，您可以使用ExpressionVisitor交换件。例如，假设我们想将“x”替换为“ln(x)”作为随机基因突变的一部分：

// 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));

使用如下实用程序：

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);
    }
}
于 2013-03-08T11:57:25.590 回答