Thursday, May 23, 2013

Expression Trees

On this post I'm going to teach you about expression trees. Expression trees are when you take an expression and build it up so that it looks like a tree. There are 2 types of calculator modes which build 2 different expression trees. Standard mode is when you take the numbers as soon as they appear in the problem. Scientific mode is when you be patient and make sure you pay attention to the operators and how much precedents each operator has.

This expression tree is for scientific mode for the problem 3*4+6/2+2*5 is:

To do the problem with an expression tree you need to collapse the nodes (numbers) with there operators (such as *,+,and/).

This is how it looks after you've done the first collapsing. You see that the 3,4,and * are gone? That's because the way you collapse is do the numbers against there operator so that you come out with the answer    .

                                            This is what you get after you do the 2nd collapsing. This time do you see the difference? Yep the /,6, and 2 are gone because I did the same thing except I divided them instead of multiplying them.

                                                This is what you get after the 3rd collapsing and its easy to spot the difference right? Well if you can't the 12,3,and the + are gone and there is a 15. That's because there was a + above the 12 and the 3 so I added them together.

                                          This is what it looks like after the 4th collapsing. The difference here is very easy to spot. The 2,5,and 2nd * are gone and instead there is a 10. That's because the * was above the 2 and 5 so I multiplied them together.

                                              This is the easiest difference to spot of all. The 10 and 15 and the + are gone and there instead there is a 25.That's because the + was above the 10 and 15 so I added them together.

Here is the assembly program to evaluate the above expression tree:

; 3 * 4 + 6 / 2 + 2 * 5
mov eax,3
mov ebx,4
mul ebx ; This collapses 3 * 4 to 12 into eax
mov ecx,eax ; This moves eax into ecx temporarily
mov eax,6
mov ebx,2
div ebx ; This collapses 6 / 2 to 3 into eax
add ecx,eax ; This collapses 3 * 4 and 6 / 2 together into 15
mov eax,2
mov ebx,5
mul ebx ; This collapses 2 * 5 to 10 into eax
add eax,ecx ; This collapses 15 and 10 into 25

No comments:

Post a Comment