If I get code written down I will post it later. Anyways here are notes on parse trees that I wrote.
===== Parse tree Notes =====
Background:
Basically with parse trees to setup the data you go through the equation one time and you tokenize it. After tokenizing it you are going to put it in the parse tree.
Note: I do parse tree in tree minor fashion instead of tree major. That is just saying basically that I am looking for the lowest element not the highest(you will see).
Ok now let's start off with a simple table of precedence.
+, - == 0
*, / == 1
So that is our simple table of precedence made for tokenizing. Now let's start with a simple expression.
5+4*5
Now let's tokenize this. In token form.
5+4*5 = 5(0)4(1)5 or simply 0,1. That was easy. Now based off of the table of precedence you should be able to figure out why that is so
.
So now how do we get that stuff into a parse tree. The logical thing and what people are taught in life is to start with multiplication in an expression like that, but in a parse tree you find the lowest element.
So in our token list 0,1 is the lowest so we put that at the top of our tree. Then we look to the left to find what argument it takes. There is a number there and no other math operators to the left of it. Now to the right of it there is a number also, but there is an operator to that side because we haven't reached the end of our token list. So since there is an operator we search for the lowest token in the rest of the list which is 1 of course. So this would start us off with
+
/ \
5 *
Now what are the two operands to * or 1. Well look to the left. There is a number and no other math operators that we haven't touched so use the number. Now look to the right and there is a number and no math operators so then we settle for the numbers. This gives us a parse tree of.
+
/ \
5 *
/ \
4 5
Great we have a parse tree but how do I solve it??? You solve by levels. Start at the lowest level and farthest to the left and start solving. So then it would be like this.
+
/ \
5 *
/ \
4 5 becomes ...
+
/ \
5 20
ok now there are no more expression to solve on the last level we did so move a level up and solve that.
+
/ \
5 20 becomes...
25
so the answer to 5+4*5 = 25
Alright now it is time to get into a little bit of history I think? Either way look at this tree again.
+
/ \
5 *
/ \
4 5
Now let's imagine a real tree and break it down into two parts. There are branches and then leaves that come off of the branches. Now the leaves are always on the outside never the inside. Now applying that to parse trees the + and * are the branch nodes because they are not on the very tip of the outside. The 5,4, and 5 are the leaf nodes because they are on the very outside.
Ok so do you notice anything? The numbers always HAVE to be in the leaf nodes and operators always HAVE to be in the branch nodes. There are no exceptions.
Now let's get into some more complicated parse trees.
(5+4)*5
uhhhh wtf that f**** up our whole tokenize thing. We are going to tokenize that the same way and then solve it wrong. D***.
But wait! There is such a thing called weighting your expression. Now let's look at this expression as we would normally tokenize it.
ToP:
+,- = 0
*,/ = 1
(5+4)*5 would be 0,1 in token form. But wait isn't that plus inside parentheses. Well exactly how many is it inside? The + is inside 1 of them. So that means we weight the expression by 1. That would give us a token list of
1,1
Now look at this expression.
((5+4))*5
the + is inside 2 of them now so we weight it by 2 which would give us
2,1 for our token list. So you should understand by now that weighting will only add the number of OPEN parentheses to the operators.
So then what is this expression.
(((5+4))*5)
Tokenized it would be: 3,2
There are 3 open when we encounter the + and only 1 open when we encounter the *. Alright after going off into that spew let's get back to the first one.
(5+4)*5
Now the token list 1,1 means we have two of the same expressions does it not? Yes technically it does but that is why I mentioned before we are doing this tree minor which means we search for the lowest token in the list that is also the farthest to the right of it. That means we would take the 1 token on the right which is the *
Now let's solve this parse tree. Look to the left and you see that * is not operating on a number but a ) so take the next lowest token in the list to the left which is 1(+). Then we look to the right of the * and find a number 5 with no expressions to the right so we use the number. Now moving on to the + we look to the left and find a number and no more expressions to the left, then we look to the right and find a number with no more expressions that we HAVE NOT used already. So that would give us a tree setup of.
*
/ \
+ 5
/ \
5 4
now solve from the lowest level on the left up.
5+4 = 9, 9 * 5 = 45!!!!
Now we will do a pretty complicated expression that I will not explain next. I will just show the expression and the respective parse tree and you should be able to figure it out through the process we went through and weighting.
Expression:
5+((4*5)+(2*5))-4
Token List:
0,3,1,3,0
Parse Tree:
-
/ \
+ 4
/ \
5 +
/ \
* *
/ \ / \
4 5 2 5
Answer:
17
Conclusion and Overview:
This maybe complicated, but aren't the good things in life complicated?? Anyways I will give you the overview of the algorithm for searching used.
Steps
1: Tokenize the list including weighting
2: Find the lowest token that is also the farthest to the right
(so in a list 1,1,1,1,1,1,1,0,1,0,2 the 0 all the way at the right before the 2 would be the first token.)
3: Find the tokens left operand
4: If there are any other UNUSED tokens to the left then
5: Find the lowest token closet to the spot you are at
5: Else use the number as your operand
6: Repeat 4-5 on the right operand respectively
7: Insert the operator into the tree and its operand as branch/leaf nodes of it
8: Repeat the steps until you are done parsing the expression
Show Posts
:thumb: