# Getting a usable expression tree

I need to get the expression tree for some expression.

expr //TreeForm


The above grabs the expression tree but it isn't in some sort of usable format. Just an image.

Level[expr, {-1}, "Heads"->True]


This does a depth first traversal of the expression tree and does give me a list of all items in the expression tree. The issue with this is that:

expr = a+b*3*c+d
{Plus, a, Times, 3, b, c, d}


and now you can see that because of the location of d I have no information on what goes where with Levels.

So the question is, is there a way for me to get the expression tree in some format where I can actually tell where everything is supposed to go?

Acceptable formats would be of the form of {operator/operatorFunctionName, symbol/value, {operator/operatorFunctionName, symbol/value, {... continues as far as can go}}, moreSymbolsRelatedToFirstOperation}

OR

{operator/operatorFunctionName, operator/operatorFunctionName, ...} {{symbol/valueForFirstOperator, ...}, {symbol/valueForSecondOperator,...}, ...}

OR any other similar format.

-
expr already is an expression tree. What format do you want? Is FullForm[expr] helpful? – Mr.Wizard Jul 31 '13 at 14:40
I recognize that it is already an expression tree. FullForm is only somewhat helpful (because I might just have to use it to parse the expression tree). Ultimately I need to do these computations in Java/SQL which is why I need the expression tree. – harageth Jul 31 '13 at 14:44
Sorry hit enter before I finished my comment... I just edited my comment to clarify why I need the expression itself in a different format. As far as a specific format.. Some sort of list. Ideally it would be some form of binary tree. But like I said above I need to pass the expression itself into Java so that I can evaluate through SQL/Java rather than Mathematica. – harageth Jul 31 '13 at 14:47
People have posted clever and simple methods for getting the form you asked for, but I want to point out that J/Link's Expr class provides a native Java representation of arbitrary Mathematica expressions. It has methods like head(), part(), length(), take(), integerQ(), etc. that you can use to analyze and deconstruct the Expr on the Java side. Just mentioning this in case you might find it easier to pass the expression intact into Java and then walk through it with Java code. – Todd Gayley Jul 31 '13 at 19:08
@ToddGayley I didn't realize that I had those functions on the Java side. I could have done it on the Java side but even with my small knowledge of mathematica it was easier in this instance to finish the rest of the parsing that I needed as well as validation through a recursive function in mathematica. – harageth Aug 1 '13 at 15:52

Please let me know if this is moving in the right direction:

expr = a + b*3*c + d;

Replace[expr, h_[x___] :> {x}, {0, -1}]

{a, {3, b, c}, d}


Given that heads are lost here, perhaps you want something like:

Replace[expr, h_[x___] :> {h, x}, {0, -1}]

{Plus, a, {Times, 3, b, c}, d}


If this is close to what you a related question that you should read is:
List manipulation to build a functional expression

Note: you may be tempted to try to simplify the code above by using ReplaceAll (short form /.) but you will find that it doesn't work. That's because the order of traversal is the opposite of Replace, despite the similar names.

-
That second one is pretty much exactly what I was wanting. Since it builds the expression itself into a list with the heads for each portion. – harageth Jul 31 '13 at 14:58
@harageth Great! I'm glad I could help. – Mr.Wizard Jul 31 '13 at 15:01
Very nice and clear. – DavidC Jul 31 '13 at 15:14

Perhaps something like this...

{#, Extract[expr, #]} & /@ Position[expr, _]


{{{0}, Plus}, {{1}, a}, {{2, 0}, Times}, {{2, 1}, 3}, {{2, 2}, b}, {{2, 3}, c}, {{2}, 3 b c}, {{3}, d}, {{}, {}}}

Breakdown

Position[expr, _] will return all of the positions of parts of expr.

{{0}, {1}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2}, {3}, {}}

Now that you know where everything is, you can use that information to retrieve the elements themselves, via the initial code.

-
FYI: "part zero" is the head of an expression, as can be seen with Plus and Times above. – Mr.Wizard Jul 31 '13 at 15:35