Thursday, October 12, 2006 1:09 PM bart

DynCalc - Dynamic compilation illustrated - Part 2: Building an expression tree

Introduction

Time for some new dynamic compilation adventures. In the previous part we took a look at the infix to postfix transformation. As an example the expression ((1+2)+3)*2-8/4 gets translated into 1 2 Add 3 Add 2 Mul 8 4 Div Sub. Today, we'll translate this postfix notation into an expression tree.

Why expression trees?

You might wonder why we need to translate this into an expression tree first (which will be covered in this post). The postfix representation is already well-suited for translation to IL. Execution then would look like this:

                             Div 
Add       Add       Mul        4     Sub
  2         3         2        8   2   2
  1    3    3    6    6   12  12  12  12  10

I agree we could simplify things, but expression trees play a prominent role in compiler techniques. More specifically, follow-up posts will travel you to the world of expression trees in C# 3.0 and LINQ, yielding to dynamic compilation of query expressions into some target domain language. I'm still working on this, so have a bit patience for this to appear online :-).

The code

Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:

static TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:

Input  1    2    Add       3         Add              2

Stack  1    2    Add(1,2)  3         Add(Add(1,2),3)  2
            1              Add(1,2)                   Add(Add(1,2),3)

I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

Of course we create some helper methods to visualize the result:

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

This is a very simple recursive tree printer. It should print something like this with our example:

+Sub
 +Mul
  +Add
   +Add
    1
    2
   3
  2
 +Div
  8
  4

So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:

+Sub     +Sub     +Sub     +Sub     +Sub     10
 +Mul     +Mul     +Mul     12       12
  +Add     +Add     6       +Div     2
   +Add     3       2        8
    1       3      +Div      4
    2      2        8
   3      +Div      4
  2        8
 +Div      4
  8
  4

But that's to be covered in the next post. Have fun!

Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:

static TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:

Input  1    2    Add       3         Add              2

Stack  1    2    Add(1,2)  3         Add(Add(1,2),3)  2
            1              Add(1,2)                   Add(Add(1,2),3)

I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

Of course we create some helper methods to visualize the result:

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

This is a very simple recursive tree printer. It should print something like this with our example:

+Sub
 +Mul
  +Add
   +Add
    1
    2
   3
  2
 +Div
  8
  4

So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:

+Sub     +Sub     +Sub     +Sub     +Sub     10
 +Mul     +Mul     +Mul     12       12
  +Add     +Add     6       +Div     2
   +Add     3       2        8
    1       3      +Div      4
    2      2        8
   3      +Div      4
  2        8
 +Div      4
  8
  4

But that's to be covered in the next post. Have fun!

Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:

static TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:

Input  1    2    Add       3         Add              2

Stack  1    2    Add(1,2)  3         Add(Add(1,2),3)  2
            1              Add(1,2)                   Add(Add(1,2),3)

I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

Of course we create some helper methods to visualize the result:

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

This is a very simple recursive tree printer. It should print something like this with our example:

+Sub
 +Mul
  +Add
   +Add
    1
    2
   3
  2
 +Div
  8
  4

So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:

+Sub     +Sub     +Sub     +Sub     +Sub     10
 +Mul     +Mul     +Mul     12       12
  +Add     +Add     6       +Div     2
   +Add     3       2        8
    1       3      +Div      4
    2      2        8
   3      +Div      4
  2        8
 +Div      4
  8
  4

But that's to be covered in the next post. Have fun!

Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:

static TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

TreeNode ToTree(Queue<MathOpOrVal> q)
{
   Stack<TreeNode> stack = new Stack<TreeNode
>();

   foreach
(MathOpOrVal mv in q)
   {
      if (mv.Value != null
)
         stack.Push(
new TreeNode
(mv.Value.Value));
      else
      {
         TreeNode
right = stack.Pop();
         TreeNode
left = stack.Pop();
         stack.Push(
new TreeNode
(mv.Op.Value, left, right));
      }
   }

   return
stack.Pop();
}

Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:

Input  1    2    Add       3         Add              2

Stack  1    2    Add(1,2)  3         Add(Add(1,2),3)  2
            1              Add(1,2)                   Add(Add(1,2),3)

I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

internal class TreeNode
{
   public TreeNode(MathOp op, TreeNode left, TreeNode
right)
   {
      Op = op;
      Left = left;
      Right = right;
   }

   public TreeNode(int
value)
   {
      Value = value;
   }

   public MathOp
? Op;
   public TreeNode
Left;
   public TreeNode
Right;
   public int
? Value;
}

Of course we create some helper methods to visualize the result:

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

static void Print(TreeNode tree)
{
   PrintTree(tree,
""
);
}

static void PrintTree(TreeNode tree, string
spacing)
{
   if (tree.Op != null
)
   {
      Console.WriteLine(spacing + "+"
+ tree.Op);
      PrintTree(tree.Left, spacing +
" "
);
      PrintTree(tree.Right, spacing +
" "
);
   }
   else
      Console
.WriteLine(spacing + tree.Value);
}

This is a very simple recursive tree printer. It should print something like this with our example:

+Sub
 +Mul
  +Add
   +Add
    1
    2
   3
  2
 +Div
  8
  4

So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:

+Sub     +Sub     +Sub     +Sub     +Sub     10
 +Mul     +Mul     +Mul     12       12
  +Add     +Add     6       +Div     2
   +Add     3       2        8
    1       3      +Div      4
    2      2        8
   3      +Div      4
  2        8
 +Div      4
  8
  4

But that's to be covered in the next post. Have fun!

kick it on DotNetKicks.com

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# Getting started with C# 3.0 Expression Trees

Wednesday, November 22, 2006 2:20 PM by B# .NET Blog

Somewhere in October this year, a series of three posts appeared online on this blog, covering "DynCalc"

# DynCalc - Dynamic Compilation Illustrated - Part 4: C# 3.0 Expression Trees

Thursday, November 23, 2006 9:09 AM by B# .NET Blog

Introduction In the previous posts on DynCalc , we explored how to write a simple parser for simple calculations,