LINQ Expression tree to generate prefix notation of expressions

Yesterday I was goint through one of the LINQ hands on lab. I was always interested by the new Expression tree in C#3.0 and one of the expression tree sample in the lab grabbed my attention. I built onto it to create a postfix notation generator from any lambda expression.

What are Expression trees

Expression tree is a very interesting concept which allows creation of in-memory expression-tree's out of lambda expressions and then manipulate/inspect the expression as data. Expression trees are created as follows

 Expression<Func<int, bool>> filter = n => !((n * 3) < 5);

Now filter contains the expression n => !((n * 3) < 5) as data and it can be manipulated and changed at will.

Pre-fix notation generation

This Expression tree is just as any other tree and can be traversed preorder to generate the prefix notation of the expression. So given the expression !((n * 3) < 5) it should be easy to generate the prefix form as in ! ( < ( * ( n 3 ) 5 )) .

I wrote up a small extension method that works on Expressions to print the post fix notation doing a preorder traversal as follows

 static void PrefixForm(this Expression exp)
{
    if (exp is BinaryExpression)
    {
        BinaryExpression binEx = (BinaryExpression)exp;
        Console.Write(" {0} ", NodeTypeLookUp[(int)binEx.NodeType]);
        Console.Write("(");
        binEx.Left.PrefixForm();
        binEx.Right.PrefixForm();
        Console.Write(")");
    }
    else if (exp is UnaryExpression)
    {
        UnaryExpression unEx = (UnaryExpression) exp;
        Console.Write(" {0} ", NodeTypeLookUp[(int)unEx.NodeType]);
        Console.Write("(");
        unEx.Operand.PrefixForm();
        Console.Write(")");

    }
    else if (exp is ParameterExpression)
    {
        Console.Write(" {0} ", ((ParameterExpression)exp).Name);
    }
    else if (exp is ConstantExpression)
    {
        Console.Write(" {0} ", ((ConstantExpression)exp).Value);
    }
    else
    {
        Console.WriteLine("{0} is not yet supported", exp.GetType().FullName);
    }
}

Expression<Func<int, bool>> filter = n => !((n * 3) < 5);<br>filter.Body.PrefixForm(); 

Not all types of expressions like method call, delegate invokes are supported here. The tree uses ExpressionType enum to represent the operators and so I wrote a lookup table to convert them to the operator they represents. I should've used the enum.GetDescription but was feeling to lazy to get that up :)

The complete code is available here. You'll need Visual Studio 8 and the Linq preview for RTM to build and run it.

Comments

• Anonymous
  March 05, 2006
  very neat exemple ;)
  
  
• Anonymous
  October 20, 2006
  The comment has been removed
• Anonymous
  July 02, 2007
  LINQ: How To Use LINQ To Query Just About Anything
• Anonymous
  September 16, 2007
  I have extended and edited a bit Your function PrefixForm: Might be interested With bests henn@sarv.ee

---

       public static void PrefixForm(this Expression exp)        {            if (exp is BinaryExpression)            {                BinaryExpression binEx = (BinaryExpression)exp;                Console.Write(" {0} ", binEx.NodeType);                Console.Write("(");                binEx.Left.PrefixForm();                Console.Write(",");                binEx.Right.PrefixForm();                Console.Write(")");            }            else if (exp is ConditionalExpression)            {                ConditionalExpression condEx = (ConditionalExpression)exp;                Console.Write(" {0} ", condEx.NodeType);                Console.Write("(");                condEx.Test.PrefixForm();                Console.Write("?");                condEx.IfTrue.PrefixForm();                Console.Write(":");                condEx.IfFalse.PrefixForm();                Console.Write(")");            }            else if (exp is UnaryExpression)            {                UnaryExpression unEx = (UnaryExpression)exp;                Console.Write(" {0} ", unEx.NodeType);                Console.Write("(");                unEx.Operand.PrefixForm();                Console.Write(")");            }            else if (exp is ParameterExpression)            {                Console.Write(" {0} ", ((ParameterExpression)exp).Name);            }            else if (exp is ConstantExpression)            {                Console.Write(" {0} ", ((ConstantExpression)exp).Value);            }            else            {                Console.WriteLine("{0} is not yet supported", exp.GetType().FullName);            }        }    }

• Anonymous
  July 04, 2010
  How the expression tree is helpful. Is there any benifit to use expression tree or it is only simplify the code structure.