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.