So I've been writing an algorithm to build a function tree and I believe I'm(adsbygoogle = window.adsbygoogle || []).push({}); aaaaallllllmostthere. The intent is to take a math function like

and build it intoCode (Text):

x^2+x+1*5

My idea to parse the function is to think of it being likeCode (Text):

/ + \

/ + \ / \

/ ^ \ x 1 * 5

x 2

where [Exp_i] represents an expression (x, a number, or a function in parentheses) and [Op_i] represents an operator. In the above functionCode (Text):

[Exp_0][Op_1][Exp_1][Op_2][Exp_2].........[Op_n][Exp_n]

I know how to write the algorithm if the operators are in order of ascending or descending precedence. For instance, something likeCode (Text):

Exp_0 = 'x'

Op_1 = '^'

Exp_1 = 2

Op_2 = '+'

Exp_2 = 'x'

Op_3 = '+'

Exp_3 = 1

Op_4 = '*'

Exp_4 = 5

is easy to build into a tree because as you grab the expressions from left to right you simply take the previous tree and make it be the left-hand side of a new tree and make the right-hand side of the tree be the current expression. The building of that tree (skipping a few steps) would look like x^2*2+1

,Code (Text):

/ ^ \

x 2

,Code (Text):

/ * \

/ ^ \ 2

x 2

The algorithm is:Code (Text):

/ + \

/ 1

/ * \

/ ^ \ 2

x 2

Hopefully that pseudo-code is legible to you.Code (Text):

Get Exp_0

If there's no Op_1, return Exp_0;

Else,

Make a tree T like

/ [Op_1] \

[Exp_0] [Exp_1]

for (i = 2; i <= n; ++i)

{

temp = T;

T = new Tree;

T.leftHandSide = temp;

T.oper = [Op_i];

T.rightHandSide = [Exp_i];

}

The algorithm for making a tree when the precedence of the operators is reversed, e.g.

is slightly more complicated, but I know how to write. I can also write an algorithm that combines the 2 algorithms I mentioned. 1+2*x^2

The problem is that I can't think of a general algorithm that looks at the precedence of each operator found and then rebuilds the tree accordingly. It seems like it would be extremely complex, and I've gotten close to making it, but maybe I'm going about things completely wrong.

Can someone give me a hint to push me along?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Having trouble with algorithm to build a function tree

Loading...

Similar Threads - Having trouble algorithm | Date |
---|---|

Have trouble running the Fermi software on ubuntu terminal | Jun 8, 2015 |

Having trouble compiling my java project. Help? | Feb 3, 2015 |

Having some trouble with Fortran | Sep 10, 2013 |

Having trouble with command prompt | Jun 24, 2008 |

Having trouble running C++ compiler | Jun 1, 2008 |

**Physics Forums - The Fusion of Science and Community**