5
$\begingroup$

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
Level[expr, {-1}, "Heads"->True]
{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.

$\endgroup$
5
  • 1
    $\begingroup$ expr already is an expression tree. What format do you want? Is FullForm[expr] helpful? $\endgroup$
    – Mr.Wizard
    Jul 31, 2013 at 14:40
  • $\begingroup$ 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. $\endgroup$
    – harageth
    Jul 31, 2013 at 14:44
  • $\begingroup$ 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. $\endgroup$
    – harageth
    Jul 31, 2013 at 14:47
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 31, 2013 at 19:08
  • $\begingroup$ @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. $\endgroup$
    – harageth
    Aug 1, 2013 at 15:52

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – harageth
    Jul 31, 2013 at 14:58
  • $\begingroup$ @harageth Great! I'm glad I could help. $\endgroup$
    – Mr.Wizard
    Jul 31, 2013 at 15:01
  • $\begingroup$ Very nice and clear. $\endgroup$
    – DavidC
    Jul 31, 2013 at 15:14
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ FYI: "part zero" is the head of an expression, as can be seen with Plus and Times above. $\endgroup$
    – Mr.Wizard
    Jul 31, 2013 at 15:35
2
$\begingroup$

In 12.3, ExpressionTree can be used to produce a usable tree:

[ExpressionTreea+b3c+d

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.