Перевод деревьев выражений

2025-06-17

В этой статье вы узнаете, как посетить каждый узел в дереве выражений при создании измененной копии этого дерева выражений. Вы переводите деревья выражений, чтобы понять алгоритмы, чтобы их можно было перенести в другую среду. Вы изменяете созданный алгоритм. Вы можете добавлять логирование, перехватывать вызовы методов и отслеживать их для различных целей.

Код, который вы создаете для перевода дерева выражений, является расширением того, что вы уже видели, чтобы посетить все узлы в дереве. При переводе дерева выражений вы посещаете все узлы и, посещая их, строите новое дерево. Новое дерево может содержать ссылки на исходные узлы или новые узлы, помещенные в дерево.

Давайте посетим дерево выражений и создадим новое дерево с некоторыми заменёнными узлами. В этом примере давайте заменим любую константу константой, которая составляет 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);

Здесь довольно много кода, но основные понятия легко усваиваются. Этот код посещает дочерние элементы в глубине первого поиска. При обнаружении постоянного узла посетитель возвращает значение константы. После того, как посетитель посетил обоих детей, эти дети вычислили сумму, вычисленную для этой поддеревки. Теперь узел сложения может вычислить сумму. После посещения всех узлов в дереве выражений сумма вычисляется. Чтобы отслеживать выполнение, запустите пример в отладчике и следите за процессом выполнения.

Упростим отслеживание того, как узлы дерева анализируются и как вычисляется сумма путем его обхода. Вот обновленная версия метода Aggregate, которая содержит много информации для трассировки.

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. Добавьте код в Main метод в файле Program.cs, чтобы создать дерево выражений и передать его в метод, который изменяет его.

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 методу этого класса. И исходные, и измененные деревья выражений выводятся для отображения изменения. Скомпилируйте и запустите приложение.

Подробнее

В этом примере показано небольшое подмножество кода, которое будет построено для обхода и интерпретации алгоритмов, представленных деревом выражений. Прочитайте эту серию Мэтта Уоррена, чтобы узнать о создании библиотеки общего назначения, которая переводит деревья выражений на другой язык. Он подробно описывает, как перевести любой код, который можно найти в дереве выражений.

Теперь вы увидели истинную мощь деревьев выражений. Вы проверяете набор кода, вносите изменения в этот код и выполняете измененную версию. Так как деревья выражений неизменяемы, вы создаете новые деревья с помощью компонентов существующих деревьев. Повторное использование узлов сводит к минимуму объем памяти, необходимой для создания измененных деревьев выражений.

Поделиться через

Перевод деревьев выражений

Обход и выполнение добавления

Создание измененной копии

Подробнее

Обратная связь

Дополнительные ресурсы