Sdílet prostřednictvím

Překlad stromů výrazů

V tomto článku se dozvíte, jak navštívit jednotlivé uzly ve stromu výrazů při vytváření upravené kopie stromu výrazů. Stromy výrazů přeložíte, abyste porozuměli algoritmům, aby bylo možné je přeložit do jiného prostředí. Změníte vytvořený algoritmus. Můžete přidat protokolování, zachytávat volání metod, sledovat je pro různé účely.

Kód, který vytvoříte pro překlad stromu výrazů, je rozšířením toho, co jste už viděli, abyste navštívili všechny uzly ve stromu. Při překladu stromu výrazů navštívíte všechny uzly a při jejich návštěvě vytvoříte nový strom. Nový strom může obsahovat odkazy na původní uzly nebo nové uzly, které jste umístili do stromu.

Prozkoumejme strom výrazů a vytvořme nový strom s několika náhradními uzly. V tomto příkladu nahradíme libovolnou konstantu konstantou, která je 10krát větší. V opačném případě ponecháte strom výrazu nedotčený. Místo čtení hodnoty konstanty a jeho nahrazení novou konstantou provedete toto nahrazení nahrazením konstantního uzlu novým uzlem, který provede násobení.

Jakmile najdete konstantní uzel, vytvoříte nový uzel násobení, jehož podřízené položky jsou původní konstantou a konstantou 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;
}

Vytvořte nový strom nahrazením původního uzlu náhradou. Změny ověříte kompilací a spuštěním nahrazeného stromu.

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

Vytvoření nového stromu je kombinace návštěv uzlů v existujícím stromu a vytvoření nových uzlů a jejich vložení do stromu. Předchozí příklad ukazuje důležitost stromů výrazů, které jsou neměnné. Všimněte si, že nový strom vytvořený v předchozím kódu obsahuje kombinaci nově vytvořených uzlů a uzlů z existujícího stromu. Uzly se dají použít v obou stromech, protože uzly v existujícím stromu nelze upravit. Opakované použití uzlů vede k významné efektivitě paměti. Stejné uzly lze použít v celém stromu nebo ve více stromech výrazů. Vzhledem k tomu, že uzly není možné upravovat, můžete stejný uzel opakovaně použít, kdykoli je to potřeba.

Procházet a provádět sčítání

Pojďme ověřit nový strom vytvořením druhého návštěvníka, který projde stromem uzlů reprezentujících sčítání a vypočítá výsledek. Proveďte nějaké úpravy na tom návštěvníkovi, kterého jste zatím viděli. V této nové verzi návštěvník vrátí částečný součet operace sčítání až do tohoto bodu. U konstantního výrazu je to jednoduše hodnota konstantního výrazu. Výsledkem výrazu sčítání je součet levého a pravého operandu, jakmile jsou tyto stromy kompletně procházeny.

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

Tady je poměrně hodně kódu, ale koncepty jsou dostupné. Tento kód navštíví děti v podrobném prvním hledání. Když narazí na konstantní uzel, návštěvník vrátí hodnotu konstanty. Poté, co návštěvník navštíví obě děti, tyto děti vypočítají součet pro tento podstrom. Uzel sčítání nyní může vypočítat součet. Po návštěvě všech uzlů ve stromu výrazů se vypočítá součet. Spuštěním ukázky v ladicím programu a trasováním provádění můžete trasovat provádění.

Zkusme usnadnit sledování toho, jak se uzly analyzují a jak se součet počítá pomocí procházení stromu. Tady je aktualizovaná verze metody Aggregate, která obsahuje poměrně hodně informací o trasování.

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");
}

Když ho spustíte ve výrazu sum , zobrazí se následující výstup:

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

Sledujte výstup a postupujte podle předchozího kódu. Měli byste být schopni zjistit, jak kód navštíví každý uzel a vypočítá součet při procházení stromem.

Teď se podíváme na další průběh, s daným výrazem sum1:

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

Tady je výstup z prozkoumání tohoto výrazu:

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

I když je konečná odpověď stejná, procházení stromu se liší. Uzly jsou procházeny v jiném pořadí, protože strom byl vytvořen s operacemi probíhajícími nejprve jiným způsobem.

Vytvoření upravené kopie

Vytvořte nový projekt konzolové aplikace . Přidejte direktivu using do souboru pro obor názvů System.Linq.Expressions. Přidejte třídu AndAlsoModifier do vašeho projektu.

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

Tato třída dědí třídu ExpressionVisitor a je specializovaná na úpravu výrazů, které představují podmíněné operace AND. Tyto operace se změní z podmíněného AND na podmíněný OR. Třída přepíše metodu VisitBinary základního typu, protože podmíněné AND výrazy jsou reprezentovány jako binární výrazy. VisitBinary Pokud výraz předaný do této metody představuje podmíněnou AND operaci, kód vytvoří nový výraz, který obsahuje podmíněný OR operátor namísto podmíněného AND operátoru. Pokud VisitBinary je předán výraz, který nepředstavuje podmíněnou AND operaci, metoda odkazuje na implementaci základní třídy. Metody základní třídy vytvářejí uzly, které připomínají předávané stromy výrazů, avšak uzly mají své podstromy nahrazené výrazovými stromy, které jsou rekurzivně vytvořeny návštěvníkem.

Přidejte direktivu using do souboru pro obor názvů System.Linq.Expressions. Do metody v souboru Program.cs přidejte kód Main , který vytvoří strom výrazu a předá ho metodě, která ji upraví.

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"))
*/

Kód vytvoří výraz, který obsahuje podmíněnou AND operaci. Pak vytvoří instanci AndAlsoModifier třídy a předá výraz Modify metodě této třídy. Původní i upravené stromy výrazů se zobrazují, aby ukázaly změnu. Zkompilujte a spusťte aplikaci.

Další informace

Tato ukázka ukazuje malou podmnožinu kódu, který byste vytvořili pro procházení a interpretaci algoritmů reprezentovaných stromem výrazu. Získejte další informace o vytvoření knihovny pro obecné účely, která překládá stromy výrazů do jiného jazyka, přečtením této série od Matta Warrena. Podrobně popisuje, jak přeložit libovolný kód, který můžete najít ve stromu výrazů.

Nyní jste poznali skutečnou sílu stromů výrazů. Prozkoumáte sadu kódu, provedete všechny změny, které chcete v kódu provést, a spustíte změněnou verzi. Vzhledem k tomu, že stromy výrazů jsou neměnné, vytvoříte nové stromy pomocí součástí existujících stromů. Opakované použití uzlů minimalizuje množství paměti potřebné k vytvoření upravených stromů výrazů.

  • Last updated on