Dividing an equation to a binary tree (did I do it right?)

MasterGod · Post by **MasterGod** » Sun Mar 30, 2008 6:22 pm

I'm studying for my exam and I'm not sure if I did it right. I didn't follow any written algorithm, I just wrote some equation and tried to make a binary tree out of it to see if I understood it right.
That's what I did:

Have I done it right ? I have no way of checking except trusting myself

Thanks.

P.S
Man I just love those kind of stuff. I can do it all night long

zeno60 · Post by **zeno60** » Sun Mar 30, 2008 6:47 pm

Been a while since I have done expression trees but from the equation I do not think you have the right tree.

Specifically on (7*8/9+4).

If you remember the order of operations when doing equations: Multiply and Division before Addition and Subtraction. (A trick we used in primary school to remember the order of operations for these was a phrase: Please Excuse My Dear Aunt Sally...P E M D A S ... Parenthesis, Exponents, Multiply...so on). Your tree would lead to the 7 being multiplyed to the answer of 8/9 when it should be the answer of 7*8 divided by 9 due to the left-hand associative rule.

Code: Select all

Since you mentioned you have no algorithm for doing trees, here is the way I was taught which made equations very simple to express as trees, first write down all the literals in the order they are given in the equations:

Code: Select all

3    2   7    2    7    2    7    8    9    4

Then in the equation, find the inner most parenthesis and box them. Continue doing this will all the parenthesis outwards splitting the equation up.

Begin with the inner box and start joining up the literals by the order of operations (Multiply before Division, Add before Subtract, etc.):
1:

Code: Select all

                   *
                 /   \
3    2   7    2     7    2    7    8    9    4

2:

Code: Select all

                                              +
                                            /   \
                                          d      \ 
                                        /   \     \
                   *                *      \      \
                 /   \            /    \     \      \
3    2   7    2     7    2    7     8     9      4

3:

Code: Select all

                                              +
                                            /   \
             +                           d      \ 
    +           \                      /   \     \
  /      *         *                *      \      \
 /     /   \     /   \            /    \     \      \
3    2    7    2     7    2    7     8     9      4

And so on, it is a lot clearer when done on old fashion pen and paper, but good luck.

MasterGod · Post by **MasterGod** » Sun Mar 30, 2008 7:01 pm

Damn it, you're right

Well, thanks!!

P.S
It seems I'll have to practice more of these things, well, it's ok cause I love it as I said.

MasterGod · Post by **MasterGod** » Sun Mar 30, 2008 7:12 pm

I've just seen your edited changes.
Well, nice work you did there.
That's a cool way to do it though the ASCII tree is a bit messy but the "algorithm" is pretty nice.

I'll remember that

Thanks.

Halifax · Post by **Halifax** » Sun Mar 30, 2008 10:42 pm

<offtopic>
I have always wanted to make an expression parser, but never conjured up the grapes to do it.

</offtopic>

zeno60 · Post by **zeno60** » Mon Mar 31, 2008 8:51 pm

Halifax wrote:<offtopic>
I have always wanted to make an expression parser, but never conjured up the grapes to do it.
</offtopic>

You should sometime. If you are in a Computer Science or equiv. pathway at school you will no doubt have to eventually, they are great way to understand grammar and semantics. Helpful if you plan to make your own language or speech-recognition software (Ironically enough I just attended a graduate seminar on that very subject; "Computer Based Recognition of Natural Language" based on a dynamic semantic model.)