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

Using All 4 General Purpose Registers (And Immediate Values)

This time we are going to do a problem that makes us use all of the registers: eax,ebx,ecx, and edx.

1+4+8+2+3+6

mov eax, 1                 ;This changes eax into a 1
mov ebx, 4                 ;This changes ebx into a 4
add eax,ebx                ;This adds eax and ebx together which changes eax into a 5
mov ecx,eax               ;This copys eax down into ecx
mov eax,8                  ;This changes eax into an 8
mov ebx,2                  ;This changes ebx into a 2
add eax, ebx               ;This adds eax and ebx together which changes eax into an A
mov edx,eax               ;This copys eax into edx
mov eax,3                   ;This changes eax into a 3
mov ebx,6                   ;This changes ebx into a 6
add eax,ebx                 ;This adds eax and ebx together which changes eax into a 9
add eax,ecx                 ;This adds eax and ecx together which changes eax into a E
add eax,edx                 ;This adds eax and edx together which changes eax into a 18 in hex

This is a contrived example (meaning I just made it up). Here is a better way to solve 1+4+8+2+3+6


;1+4+8+2+3+6
mov eax,1
mov ebx,4
add eax,ebx
mov ebx,8
add eax,ebx
mov ebx,2
add eax,ebx
mov ebx,3
add eax,ebx
mov ebx,6
add eax,ebx

But we don't need to store numbers in registers before we use them.


;1+4+8+2+3+6
mov eax,1
add eax,4
add eax,8
add eax,2
add eax,3
add eax,6

You see? We didn't need to use any registers because those numbers are immediately available so it saves time because that way you don't have to go pull the number out of a register.  That's why these numbers are called immediate values.

Registers

I'm going to write a program to add 2, and 7 then I'll explain how it works after.

mov eax,2
mov ebx,7
add eax,ebx

That should be the weirdest thing I've shown you in all of my posts right? Well the eax and ebx are the names of registers which are parts in a computer. And the mov is actually the word move but in computers we spell it m o v so when I say mov eax,2 I'm saying put a 2 in eax. ebx is another register but eax is the main register. Registers aren't big parts in a computer they are inside the C.P.U which is a tiny part of a computer that does all the thinking. There are 32 bits (binary digits) in a register. Now we'll go over the program again and I'll show you line by line what goes on with the registers.

mov eax,2       ; This changes the eax register to a 2
mov ebx,7       ; This changes the ebx register to a 7                                                                        
add eax,ebx     ; This adds eax and ebx which changes eax into a 9

Sometimes the problems are long so you need other registers such as ecx and edx to hold the answers.
Now let's try a more complicated example.


1+4+5+3+4+6

mov eax,1              ;This will change eax into a 1
mov ebx,4              ;This will change ebx into a 4
add eax,ebx            ;This will add eax and ebx together which will change eax into a 5
mov ecx,eax           ;This will copy eax into ecx
mov eax,5              ;This will change eax into a 5
mov ebx,3              ;This will change ebx into a 3
add eax,ebx            ;This will add eax and ebx together which will change eax into an 8
add eax,ecx            ;This will add eax and ecx together which will change eax into a 13
mov edx,eax           ;This will copy eax into edx
mov eax,4              ;This will change eax into a 4
mov ebx,6              ;This will change ebx into a 6
add eax,ebx            ;This will add eax and ebx together which will change eax into a 10
add eax,edx            ;This will add eax and ebx together which will change eax into a 23

Adding Binary/Adding Hex

It's simple to add binary numbers but a little hard to add hex numbers. We'll start with binary.

  1010

+0101

  1111

See? It's easy! All you have to do is add 1+0 but it gets a little harder.

       1

   1001

 +0101

   1110

Do you see how there was a 1+1 in there? When that happens you put a zero there and put a 1 over the one behind it.

   1    1

   0101

 +0011

   1111       

How you add hex isn't very easy. If you know how to count in hex it's easier though.

   8
 +2
  A

You would think I should have put a ten there right? Well in hex it doesn't work that way because A=10 in hex.

   9
 +3
   C
When you start to overlap it get's even harder.

    8
  +8
  10


Now that must look even weirder right? Because normally you would say 8+8=16. Well 1 0 is actually the first number you get to when you overlap. The next numbers in hex are 11,12,13,14,15,16,17,18,19,1A,1B,1C,1D,1E,1F,20,21,22,23,24,25,26 etc.

Hex and How it Works

Since my dad taught me about hex I thought I should put it in one of my posts.


This is how you count to 15 in hex.
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

Looks pretty weird huh? Well believe it or not those letters are numbers in hex!

A=10
B=11
C=12
D=13
E=14
F=15

Since there are more digits before you overlap numbers that look like decimal numbers are actually
much higher.For example:
                                         10 in hex = 16 in decimal

Lets count to 20 in decimal then count to 20 in hex.
                 

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20

1  2   3  4   5  6  7  8  9  A  B  C  D  E  F  10  11  12  13  14

I'm sure there are some differences you notice very quickly. The reason the numbers after F look like 10 to 14 is because the 1 tells how many 16's there are and the number after shows how many 1's there are.
This time were going to count to 20 in hex then were going to count to 20 in binary.

0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14

0000  0001  0010  0011  0100  0101  0110  0111  1000  1001  1010  1011  1100  1101  1110  1111 10000 10001 10010 10011 10100

Binary and hex are related in a way can you see it? (If you can't the answers at the bottom of the page.)

The reason we use hex is because computers think in binary and if they showed numbers in binary there would be so many 1's and 0's it would take forever to figure out what the number was. So we abstract binary digits into hex digits to make it easier to show the numbers. 1 hex number = 4 binary digits which =1 nibble. So the way to convert binary numbers into hex is simple.

1011  1010  0111  1111  1110  1100
 D       A       7        F        E       C

Answer: Binary and hex are related because both of them add an extra digit when they get to 16 because they both overlap at 16.

Binary Numbers - How it all began

My dad started teaching me about a month ago and he started with binary. I liked doing it so he decided to teach me everything he knew. After I got the point of binary we started hex.It was very fun!So we had classes in the mornings. After about 2 weeks he taught me about the registers inside
a computer and how they work. I also started an account on typing web so I'm learning how to type.
Then he taught me how to do math problems using the registers. Then he taught me how to use RAM.


In binary there is only 2 digits 0, and 1. You will get mixed up if you don't know that. The thing is in
normal counting you have ten digits before you overlap 1, 2, 3, 4, 5, 6, 7, 8, 9 in binary it's the same
thing except you only have 2 digits.In normal counting you have the 1's column, the 10's column, the
100's column,and the 1000's column. In binary it's the same thing except there's the 1's column, the
2's column, the 4's column, and the 8's column. Just like in decimal (normal counting) you add the
digits column by column. For example: 1010 binary equals 10 decimal because there is zero 1's,one 2,zero 4's,and one 8.

This is how you count in binary to 10.	This is how you convert (change it into) a binary number into a decimal number.
0001=1 0010=2   0011=3   0100=4   0101=5   0110=6   0111=7 1000=8 1001=9 1010=10	For example:  1101 converts to  1 1 0 1  8+4+0+1=13

This is how you convert a decimal number to a binary number.

12 converts to

1  1  0  0

8+4+0+0=12