轉譯運算式樹狀架構

文章
05/22/2023

在本文中，您將了解如何瀏覽運算式樹狀架構中的每個節點，同時建立修改後的運算式樹狀架構複本。您將執行運算式樹狀架構以了解演算法，以便可將該演算法轉譯至其他環境。您可變更已建立的演算法。您可新增記錄、攔截和追蹤方法呼叫或用於其他目的。

您為了轉譯運算式樹狀架構所建立的程式碼，就是您已看到可瀏覽樹狀中所有節點的運算式。當您轉譯運算式樹狀架構時，您會瀏覽所有節點，並在瀏覽時建立新的樹狀。新的樹狀架構可能包含原始節點的參考，或是您已置於樹狀架構的新節點參考。

讓我們瀏覽運算式樹狀架構，然後取代一些節點來建立新的樹狀架構。在此範例中，讓我們將任何常數取代為 10 倍大的常數。否則，您會保持運算式樹狀架構不變。您不會讀取常數值並取代為新常數，而是將常數值取代為執行乘法運算的新節點，來進行這項取代。

在這裡，找到常數節點之後，請建立新的乘法節點，其子系為原始常數和常數 10：

private static Expression ReplaceNodes(Expression original)
{
    if (original.NodeType == ExpressionType.Constant)
    {
        return Expression.Multiply(original, Expression.Constant(10));
    }
    else if (original.NodeType == ExpressionType.Add)
    {
        var binaryExpression = (BinaryExpression)original;
        return Expression.Add(
            ReplaceNodes(binaryExpression.Left),
            ReplaceNodes(binaryExpression.Right));
    }
    return original;
}

將原始節點取代為替代節點以建立新的樹狀架構。您會藉由編譯和執行已被取代的樹狀架構來進行驗證。

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var addition = Expression.Add(one, two);
var sum = ReplaceNodes(addition);
var executableFunc = Expression.Lambda(sum);

var func = (Func<int>)executableFunc.Compile();
var answer = func();
Console.WriteLine(answer);

建立新的樹狀結合了瀏覽現有樹狀中的所有節點，以及建立新的節點並將其插入樹狀。先前範例示範運算式樹狀架構不可變的重要性。請注意，以先前程式碼建立的新樹狀架構包含新建立節點及來自現有樹狀架構節點的組合。節點可在這兩個樹狀架構中使用，因為無法修改現有樹狀架構中的節點。重新使用節點會大幅提升記憶體的效率。您可以在整個樹狀中，或在多個運算式樹狀架構中使用相同的節點。由於無法修改節點，因此可在需要時重複使用相同的節點。

周遊和執行加法

讓我們來驗證樹狀架構，請建立第二個造訪者來查核加法節點的樹狀並計算結果。對您到目前為止所看到的造訪者進行一些修改。在此新版本中，造訪者會傳回加法運算到目前為止的部分總和。對於常數運算式，這會是常數運算式的值。對於加法運算式，結果會是在周遊這些樹狀之後的左右運算元總和。

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var three = Expression.Constant(3, typeof(int));
var four = Expression.Constant(4, typeof(int));
var addition = Expression.Add(one, two);
var add2 = Expression.Add(three, four);
var sum = Expression.Add(addition, add2);

// Declare the delegate, so you can call it
// from itself recursively:
Func<Expression, int> aggregate = null!;
// Aggregate, return constants, or the sum of the left and right operand.
// Major simplification: Assume every binary expression is an addition.
aggregate = (exp) =>
    exp.NodeType == ExpressionType.Constant ?
    (int)((ConstantExpression)exp).Value :
    aggregate(((BinaryExpression)exp).Left) + aggregate(((BinaryExpression)exp).Right);

var theSum = aggregate(sum);
Console.WriteLine(theSum);

這裡的程式碼很多，但概念很容易了解。此程式碼會瀏覽第一次深度搜尋的子系。當它遇到常數節點時，造訪者會傳回常數值。造訪者瀏覽兩個子系之後，這些子系就會計算針對該樹狀子目錄計算得來的總和。加法節點現在可以計算其總和。瀏覽運算式樹狀架構中的所有節點之後，就會計算總和。您可以執行偵錯工具中的樣本並追蹤執行情況，來追蹤執行情況。

藉由周遊此樹狀，可讓我們更輕鬆地追蹤節點的分析方式，以及總和的計算方式。以下是彙總方法的更新版本，其中包含相當多的追蹤資訊：

private static int Aggregate(Expression exp)
{
    if (exp.NodeType == ExpressionType.Constant)
    {
        var constantExp = (ConstantExpression)exp;
        Console.Error.WriteLine($"Found Constant: {constantExp.Value}");
        if (constantExp.Value is int value)
        {
            return value;
        }
        else
        {
            return 0;
        }
    }
    else if (exp.NodeType == ExpressionType.Add)
    {
        var addExp = (BinaryExpression)exp;
        Console.Error.WriteLine("Found Addition Expression");
        Console.Error.WriteLine("Computing Left node");
        var leftOperand = Aggregate(addExp.Left);
        Console.Error.WriteLine($"Left is: {leftOperand}");
        Console.Error.WriteLine("Computing Right node");
        var rightOperand = Aggregate(addExp.Right);
        Console.Error.WriteLine($"Right is: {rightOperand}");
        var sum = leftOperand + rightOperand;
        Console.Error.WriteLine($"Computed sum: {sum}");
        return sum;
    }
    else throw new NotSupportedException("Haven't written this yet");
}

在 sum 運算式中執行此方法會產生下列輸出：

10
Found Addition Expression
Computing Left node
Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Constant: 2
Right is: 2
Computed sum: 3
Left is: 3
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 10
10

追蹤輸出並依照上述程式碼進行。您應該能夠了解程式碼如何在周遊樹狀時瀏覽每個節點並計算總和，然後求得總和。

現在，讓我們來看一個不同的執行，其運算式是由 sum1 提供：

Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));

以下是查看此運算式後的輸出：

Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 2
Left is: 2
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 9
Right is: 9
Computed sum: 10
10

雖然最後的解都相同，但樹狀周遊則不同。這些節點會依不同順序周遊，因為樹狀建構後所出現的第一個作業不同。

建立已修改的樹狀架構

建立新的主控台應用程式專案。將 using 指示詞新增至 System.Linq.Expressions 命名空間的檔案。將 AndAlsoModifier 類別新增至專案。

public class AndAlsoModifier : ExpressionVisitor
{
    public Expression Modify(Expression expression)
    {
        return Visit(expression);
    }

    protected override Expression VisitBinary(BinaryExpression b)
    {
        if (b.NodeType == ExpressionType.AndAlso)
        {
            Expression left = this.Visit(b.Left);
            Expression right = this.Visit(b.Right);

            // Make this binary expression an OrElse operation instead of an AndAlso operation.
            return Expression.MakeBinary(ExpressionType.OrElse, left, right, b.IsLiftedToNull, b.Method);
        }

        return base.VisitBinary(b);
    }
}

此類別會繼承 ExpressionVisitor 類別，並針對代表 AND 條件運算的運算式進行修改。它會將這些運算從 AND 條件運算變更為 OR 條件運算。此類別會覆寫基底類型的 VisitBinary 方法，因為 AND 條件運算式會以二元運算式來表示。在 VisitBinary 方法中，如果傳遞給它的運算式代表 AND 條件運算，程式碼會建構新的運算式，以包含 OR 條件運算子來取代 AND 條件運算子。如果傳遞給 VisitBinary 的運算式不代表 AND 條件運算，此方法會延後到基底類別實作。基底類別方法會建構類似所傳入運算式樹狀架構的節點，但這些節點的樹狀子目錄會由造訪者以遞迴方式產生的運算式樹狀架構來取代。

將 using 指示詞新增至 System.Linq.Expressions 命名空間的檔案。將程式碼新增至 Program.cs 檔案中的 Main 方法以建立運算式樹狀架構，然後將運算式樹狀架構傳遞給要修改其內容的方法。

Expression<Func<string, bool>> expr = name => name.Length > 10 && name.StartsWith("G");
Console.WriteLine(expr);

AndAlsoModifier treeModifier = new AndAlsoModifier();
Expression modifiedExpr = treeModifier.Modify((Expression)expr);

Console.WriteLine(modifiedExpr);

/*  This code produces the following output:

    name => ((name.Length > 10) && name.StartsWith("G"))
    name => ((name.Length > 10) || name.StartsWith("G"))
*/

此程式碼會建立包含 AND 條件運算的運算式。然後建立 AndAlsoModifier 類別的執行個體，並將運算式傳遞給此類別的 Modify 的方法。此時會輸出原始和修改後的運算式樹狀架構，以顯示變更的情形。編譯並執行應用程式。

深入了解

此範例顯示您所建立的一小部分程式碼，該程式碼會用來周遊及解譯由運算式樹狀架構表示的演算法。如需建立一般用途程式庫 (以將運算式樹狀架構轉譯為其他語言) 的詳細資訊，請參閱 Matt Warren 所撰寫的這一系列。該系列進一步詳細說明如何將您可能在運算式樹狀架構中找到的任何程式碼進行轉譯。

您現在已了解運算式樹狀架構的真正強大之處。您會查看一組程式碼、對該程式碼進行任何想要的變更，然後執行變更後的版本。因為運算式樹狀架構為不可變，所以您會使用現有樹狀的元件來建立新的樹狀。重新使用節點即可降低建立修改後的運算式樹狀架構所需的記憶體數量。

分享方式：

轉譯運算式樹狀架構

周遊和執行加法

建立已修改的樹狀架構

深入了解

更多資源