I know the answer (it's 42)

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