Bagikan melalui

Menerjemahkan pohon ekspresi

Dalam artikel ini, Anda mempelajari cara mengunjungi setiap simpul di pohon ekspresi sambil membangun salinan pohon ekspresi yang dimodifikasi. Anda menerjemahkan pohon ekspresi untuk memahami algoritma sehingga dapat diterjemahkan ke lingkungan lain. Anda mengubah algoritma yang telah dibuat. Anda dapat menambahkan pengelogan, mencegat panggilan metode dan melacaknya, atau tujuan lainnya.

Kode yang Anda buat untuk menerjemahkan pohon ekspresi adalah ekstensi dari apa yang telah Anda lihat untuk mengunjungi semua simpul di pohon. Saat Anda menerjemahkan pohon ekspresi, Anda mengakses semua simpul, dan saat mengaksesnya, membangun pohon baru. Pohon baru mungkin berisi referensi ke simpul asli, atau simpul baru yang telah Anda tempatkan di pohon.

Mari kita kunjungi pohon ekspresi, dan buat pohon baru dengan beberapa simpul pengganti. Dalam contoh ini, mari kita ganti konstanta apa pun dengan konstanta yang 10 kali lebih besar. Jika tidak, Anda membiarkan pohon ekspresi tetap utuh. Daripada membaca nilai konstanta dan menggantinya dengan konstanta baru, Anda membuat penggantian ini dengan mengganti simpul konstanta dengan simpul baru yang melakukan perkalian.

Di sini, setelah Anda menemukan simpul konstanta, Anda membuat simpul perkalian baru yang anak-anaknya adalah konstanta asli dan konstanta 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;
}

Buat pohon baru dengan mengganti simpul asli dengan pengganti. Anda memverifikasi perubahan dengan mengkompilasi dan menjalankan pohon yang diganti.

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

Membangun pohon baru adalah kombinasi mengunjungi simpul di pohon yang ada, dan membuat simpul baru dan memasukkannya ke dalam pohon. Contoh sebelumnya menunjukkan pentingnya pohon ekspresi yang tidak dapat diubah. Perhatikan bahwa pohon baru yang dibuat dalam kode sebelumnya berisi campuran simpul yang baru dibuat, dan simpul dari pohon yang ada. Simpul dapat digunakan di kedua pohon karena simpul di pohon yang ada tidak dapat dimodifikasi. Pendaur-ulangan simpul menghasilkan efisiensi memori yang signifikan. Simpul yang sama dapat digunakan di seluruh pohon, atau di beberapa pohon ekspresi. Karena simpul tidak dapat dimodifikasi, simpul yang sama dapat digunakan kembali setiap kali diperlukan.

Menelusuri dan melakukan penambahan

Mari kita verifikasi pohon baru dengan membangun pengunjung kedua yang menelusuri pohon simpul penambahan dan menghitung hasilnya. Buat beberapa modifikasi pada pengunjung yang telah Anda lihat sejauh ini. Dalam versi baru ini, pengunjung mengembalikan jumlah parsial dari operasi penambahan sampai titik ini. Untuk ekspresi konstanta, itu hanya nilai ekspresi konstanta. Untuk ekspresi penjumlahan, hasil yang diperoleh adalah penjumlahan dari operand yang kiri dan yang kanan, setelah pohon tersebut dilalui.

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

Ada sedikit kode di sini, tetapi konsepnya dapat didekati. Kode ini mengunjungi anak-anak dalam pencarian pertama yang mendalam. Ketika menemukan simpul konstanta, pengunjung mengembalikan nilai konstanta. Setelah pengunjung mengunjungi kedua anak, anak-anak tersebut telah menghitung jumlah yang dihitung untuk subtree itu. Simpul tambahan sekarang dapat menghitung hasil dari penjumlahan. Setelah semua simpul di pohon ekspresi matematika dikunjungi, hasil penjumlahan telah dihitung. Anda dapat melacak eksekusi dengan menjalankan sampel di debugger dan melacak eksekusi.

Mari kita permudah menelusuri bagaimana simpul dianalisis dan cara menghitung jumlah dengan melalui pohon. Berikut adalah versi terbaru dari metode Agregat yang mencakup sedikit informasi pelacakan:

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

Menjalankannya pada sum ekspresi menghasilkan output berikut:

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

Lacak output dan ikuti dalam kode sebelumnya. Anda harus dapat mengetahui bagaimana kode mengunjungi setiap simpul dan menghitung jumlah saat melewati pohon dan menemukan jumlahnya.

Sekarang, mari kita lihat eksekusi yang berbeda, dengan ekspresi yang diberikan oleh sum1:

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

Berikut adalah output dari memeriksa ekspresi ini:

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

Meskipun jawaban akhirnya sama, traversal pohon berbeda. Simpul dilalui dalam urutan yang berbeda, karena pohon dibangun dengan operasi yang berbeda dilakukan terlebih dahulu.

Membuat salinan yang dimodifikasi

Buat proyek Aplikasi Konsol baru. Tambahkan direktif using ke file untuk System.Linq.Expressions namespace. Tambahkan kelas AndAlsoModifier ke proyek Anda.

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

Kelas ini mewarisi ExpressionVisitor kelas dan dikhususkan untuk memodifikasi ekspresi yang mewakili operasi kondisional AND . Ini mengubah operasi ini dari kondisi AND menjadi kondisi OR. Kelas mengambil alih VisitBinary metode jenis dasar, karena ekspresi bersyarat AND diwakili sebagai ekspresi biner. Dalam metode VisitBinary, jika ekspresi yang diteruskan ke dalamnya mewakili operasi bersyarat AND, kode membuat ekspresi baru yang berisi operator kondisional OR alih-alih operator kondisional AND. Jika ekspresi yang diteruskan ke VisitBinary tidak mewakili operasi bersyarat AND, metode mengacu pada implementasi kelas dasar. Metode kelas dasar membuat simpul yang seperti pohon ekspresi yang diteruskan, tetapi simpul memiliki sub pohonnya diganti dengan pohon ekspresi yang dihasilkan secara rekursif oleh pengunjung.

Tambahkan direktif using ke file untuk System.Linq.Expressions namespace. Tambahkan kode ke Main metode dalam file Program.cs untuk membuat pohon ekspresi dan meneruskannya ke metode yang memodifikasinya.

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

Kode membuat ekspresi yang berisi operasi bersyarah AND . Kemudian, dibuat sebuah instans dari kelas AndAlsoModifier dan ekspresinya diteruskan ke metode Modify dari kelas tersebut. Pohon ekspresi asli dan yang dimodifikasi dihasilkan untuk menampilkan perubahan. Kompilasi dan jalankan aplikasi.

Pelajari lebih lanjut

Sampel ini menunjukkan subset kecil kode yang akan Anda buat untuk melintasi dan menginterpretasikan algoritma yang diwakili oleh pohon ekspresi. Untuk informasi tentang membangun pustaka tujuan umum yang menerjemahkan pohon ekspresi ke dalam bahasa lain, baca seri ini oleh Matt Warren. Ini menjelaskan secara rinci cara menerjemahkan kode apapun yang mungkin Anda temukan di pohon ekspresi.

Anda sekarang telah melihat kekuatan sebenarnya dari pohon ekspresi. Anda memeriksa sekumpulan kode, membuat perubahan apa pun yang Anda inginkan untuk kode tersebut, dan menjalankan versi yang diubah. Karena pohon ekspresi tidak dapat diubah, Anda membuat pohon baru dengan menggunakan komponen pohon yang ada. Menggunakan kembali simpul meminimalkan jumlah memori yang diperlukan untuk membuat pohon ekspresi yang dimodifikasi.

  • Last updated on