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ávání volání metod a sledovat je nebo jiné úč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.
Pojďme navštívit strom výrazů a vytvořit nový strom s některými 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ázení a spuštění sčítání
Pojďme nový strom ověřit vytvořením druhého návštěvníka, který provede strom sčítání uzlů a vypočítá výsledek. Proveďte několik úprav návštěvníka, 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ých a pravých operandů, jakmile jsou tyto stromy 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. Když návštěvník navštíví obě děti, vypočítaly součet vypočítaný pro tento podstrom. Uzel sčítání teď může vypočítat jeho 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í.
Pojďme snadněji sledovat, jak se uzly analyzují a jak se součet počítá procházením stromu. Tady je aktualizovaná verze metody Aggregate, která obsahuje poměrně málo 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 a najde součet.
Teď se podíváme na jiné spuštění s 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 se cestují v jiném pořadí, protože strom byl vytvořen s různými operacemi, ke kterým došlo jako první.
Vytvoření upravené kopie
Vytvořte nový projekt konzolové aplikace . using Přidejte do souboru direktivu System.Linq.Expressions pro obor názvů. Přidejte do AndAlsoModifier projektu třídu.
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 a je specializovaná na úpravu ExpressionVisitor výrazů, které představují podmíněné AND operace. 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 výraz, který VisitBinary je předán, nepředstavuje podmíněnou AND operaci, metoda deferuje na implementaci základní třídy. Metody základní třídy vytvářejí uzly, které se podobají stromům výrazů, které se předávají, ale uzly mají své dílčí stromy nahrazené stromy výrazů vytvořenými návštěvníkem rekurzivně.
using Přidejte do souboru direktivu System.Linq.Expressions pro obor názvů. 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 změněné stromy výrazů se zobrazí tak, aby se změna zobrazila. 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. Informace o vytvoření knihovny pro obecné účely, která překládá stromy výrazů do jiného jazyka, si přečtěte tuto sérii matta Warrena. Podrobně popisuje, jak přeložit libovolný kód, který můžete najít ve stromu výrazů.
Teď jste viděli 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ů.
