I don't understand why every professor on earth won't look at this video and explain it like that. Most of my professors are always teaching these trivial information in a really complicated way. Thanks a lot!
A true expression tree is built by parsing the input using a grammar based around expressions, this hasn't been on the a level computer science specification since before 2000. Search for expression trees and bnf for more details on building real expression trees
my teacher taught me another method of how to traverse nodes, but this one was epic! I am taking computing 9691 CIE, and even in the course book, the method is not as good as yours. hats off to you! :)
I have a question i didn't hear what you say when you put the power in the same level with f,k you say something about it . can anyone get me this idea straight?
I noticed that if I tried to draw the tree with the branches the same length i would run out of room, so before drawing the power node i extended the right branch to give me more room
Like this, Unary minus is highest precedence, Mod is same as mult and divide drive.google.com/file/d/1tJvsiBRG3e-AylK179iXHhGIP2Wwp0dX/view?usp=sharing
1:03 "Is everyone happy with that?" - no - the exponent should be done before since it has higher precedence than the plus and the minus in the brackets before that due to the brackets. Arbitrarily adding in brackets changes the meaning of the expression!
using that logic the exponent operator would be done before the assignment operator. It will be done before the minus but the plus comes before the minus which is at the same level of precedence and therefore left to right evaluation occurs. If you use a stack to convert the reverse polish you will get the same answer as the tree walk which is gfk+pds-^-=
But surely the assignment operator should be the last operator to be used right? I mean it's no good assigning when you've not calculated what it is you want to assign beforehand. I've no idea how this left-to-right evaluation is supposed to work as all I can see as the order of that equation is: 1. d - s 2. p ^ (d - s) 3. f + k 4. (f + k) - (p ^ (d - s)) 5. g = ((f + k) - (p ^ (d - s))) Also, how does having the expression in Reverse Polish Notation help equate the answer? If anything it is harder as if you have multiple digit numbers in the expression, you've just lost the operators acting as delimiters between them so you can't tell if 398- is 39 - 8 or 3 - 98.
The assignment operator is the last operator executed. A compiler cannot process infix, so the expression has to be in reverse polish so the compiler can generate the machine code to calculate the expression, as the data is seen by the time the operation is needed
I finally managed to write a program to evaluate infix! It just recurse-calls its own expression parsing logic whenever it encounters an open bracket then when it reaches the corresponding close bracket, it has incremented the character index to that point and can exit the recursion.
His postfix expression is incorrect.....even his tree is not following operator precedence.... If tree construction followed operator precedence. Then the final postfix answer should be "g=f+R-p^d-s
Hùng Doãn Phi I didn't skip it, taught my students this but never bothered doing a video, but it's generally not asked in our specification. It's not that hard anyway you just need to make sure you leave gaps as you go. Here's how to do it (taken from my notes on reverse polish) Converting Postfix back to Infix to preserve precedence ============================================= We can see that if we try to go from an expression tree back to Infix we lose the precedence overrides implicit in the tree. If we need to get back to the Infix expression we can use the Postfix form from the tree. Here is the process: 1. Start at the first item in the Postfix string 2. If item is an operand right it down and leave a gap go to 4 3. If item is an operator write it down in the first available gap between operands and place parenthesis around the operands go to 4 4. Move to next item if it exists and go to 2 5. Remove last brackets placed then attempt to remove all brackets where precedence is not overwritten Using the 3 examples shown we will take the postfix and generate the original Infix expressions, we will start a new line where we encounter an operator and add the parenthesis. Ex1 Postfix: a b c * + a b c a (b * c) (a + (b * c) ) a + (b * c) outside brackets not necessary Infix: a + b * c other brackets not necessary as * is higher than + Ex2 Postfix: a b + c * a b (a + b) c ((a + b) * c) outside brackets not necessary Infix: (a + b) * c final brackets necessary as these override precedence between + and * Ex3 Postfix: g h d + f e k + * - = g h d g (h + d) f e k g (h + d) f (e + k) g (h + d) (f * (e + k) ) g ( (h + d) - (f * (e + k) ) ) (g = ((h + d) - (f * (e + k) ) ) ) g = ((h + d) - (f * (e + k) ) ) outside brackets not necessary g = (h + d) - (f * (e + k) ) outside brackets only surround right hand of assignment g = h + d - (f * (e + k) ) brackets not necessary between + and - evaluate left to right g = h + d - f * (e + k) brackets not necessary between * and - as * is already higher precedence Infix: g = h + d - f * (e + k) final brackets override precedence between * and + so necessary
HurrayBanana wow I never thought you would mind answering my question. thank you, sir, but I think you misunderstand my question. I meant you taught us how to create an expression tree from an infix that is helpful, but to do so we need an input expression which is already added brackets in a formatted way like: ((a+b)/c)+(d/e). But when we create a program, it is not only required the accuracy but also convenience for users. And normally, when inputting an expression, people will enter (a+b)/c+d/e instead of ((a+b)/c)+(d/e). So before building an expression tree, we need to adjust the input expression to the form we need. My idea is to store the expression in an array of string (each element of the array will store an operator, an operand, or even a smaller expression which is already added brackets in the way we need). Then we will step by step combine 2 small expressions and an operand between them to bigger expression: A, B, and + become (A+B) // 3 elements become 1 element C, D, and * become (C*D) // 3 elements become 1 element (A+B), (C*D), and / became ((A+B)/(C*D)) // 3 elements become 1 element ... At last we get the first element of the array as the string of the expression we need I think my solution is quite complex, hope you can give me a better way to do this. Sorry for my bad English!
Hùng Doãn Phi No problems but you don't need to add extra brackets taking your example ( I've mentioned which symbol i am parsing as the font spacing is not predictable) (a+b)/c+d/e just use the stack to convert parse Item 1 ( ============ (a+b)/c+d/e ^ | | | | | | ------- stack empty so push ( on stack rpn currently empty | | | ( | ------- stack parse Item 2 a ============ (a+b)/c+d/e ^ write down a rpn currently a | | | ( | ------- stack parse Item 3 + ============ (a+b)/c+d/e ^ higher precedence than ( so push on stack rpn currently a | | | + | | ( | ------- stack parse Item 4 b ============ (a+b)/c+d/e ^ write down b rpn currently ab | | | + | | ( | ------- stack parse Item 5 ) ============ (a+b)/c+d/e ^ pop contents of stack up to ( and discard ( rpn currently ab+ | | | | | | ------- stack - empty parse Item 6 / ============ (a+b)/c+d/e ^ stack empty so push / on stack rpn currently ab+ | | | | | / | ------- stack parse Item 7 c ============ (a+b)/c+d/e ^ write down c rpn currently ab+c | | | | | / | ------- stack parse Item 8 + ============ (a+b)/c+d/e ^ + not higher precedence than what is on stack, so pop / from stack stack now empty so push + rpn currently ab+c/ | | | | | + | ------- stack parse Item 9 d ============ (a+b)/c+d/e ^ write down d rpn currently ab+c/d | | | | | + | ------- stack parse Item 10 / ============ (a+b)/c+d/e ^ / higher precedence than top of stack so push rpn currently ab+c/d | | | / | | + | ------- stack parse Item 11 e ============ (a+b)/c+d/e ^ write down e rpn currently ab+c/de | | | / | | + | ------- stack Final step dump the stack ========================= finished parsing input so pop entire contents of stack rpn currently ab+c/de/ | | | | | + | ------- stack rpn currently ab+c/de/+ | | | | | | ------- stack - empty
HurrayBanana Thanks a lot. I was thinking about how to get a postfix expression from the infix, but I could only do with the infix expression which doesn't contain brackets. Now I will try your solution. By the way, I think your lecture is easy to understand, you are very good at explaining to people, but you don't need to go too deep to the details, just give your students the way, and let them go by themselves
I don't understand why every professor on earth won't look at this video and explain it like that. Most of my professors are always teaching these trivial information in a really complicated way. Thanks a lot!
@Daniel Madden wow 😳😲
Left Right Root! Left Right Root! Left Right Root! I just lost track with that .... This is a great explanation!!! Thank you
PostFix conversion starts at 5:40 ... Thanks for such a good explanation...
👌
Wow, you're explanation/method was infinitely better than my CS professors. Thanks so much!
Thanks
one word: brilliant! Thank you very much. The Internet is full of crap, but people like you remind me why it is a great invention!
Brilliant illustration. Loved it
Thank you very much! only video that made sense
Simple yet effective explanation..don't know why my professor makes it complex
Thank you
You are a Genius, my very good friend Haadee recommended you to me. I shall remember you forever when I pass my degree. You are a legend !
That line technique was wonderful, i sorted out the rest myself i.e. preorder and inorder. Keep up the good work. Many thanks
You sir helped understand this easily. This is a great approach.
no problem mate, that was the idea
Really clear explanation and high video quality, thanks a lot =)
+Othman Alikhan Happy to be of some help
Wish I had teachers like you, very nice and clear
u sir have helped me for this exam greatly u shall be be friend in the next life
nice
Oh my God. I didn't thought this approach.Thank you.
Excellent!
this guy is awesome. i wish he was my teacher
Fantastic. 💕
Much better than my A-Level teacher.
Can't we either convert infix to prefix or postfix first and then construct an expression tree from it with an easy algorithm?
A true expression tree is built by parsing the input using a grammar based around expressions, this hasn't been on the a level computer science specification since before 2000. Search for expression trees and bnf for more details on building real expression trees
very very useful sir.IT is mind blogging.
Oh shit. This video totally helped me. Thanks man.
thank you sir !!!u really made it clear
my teacher taught me another method of how to traverse nodes, but this one was epic! I am taking computing 9691 CIE, and even in the course book, the method is not as good as yours. hats off to you! :)
+Fever Del Rey Thanks very much, hope I've helped a little bit cheers
thanks. you made it look easy
Simple and easy to understand. Thanks
Cheers
i love it
And to change it to prefix we traverse it the same but mark the line to the left of each node? Does it work?
Yep
Holy that's so useful thanks.
thanks for this video sir::
I have a question i didn't hear what you say when you put the power in the same level with f,k you say something about it .
can anyone get me this idea straight?
I noticed that if I tried to draw the tree with the branches the same length i would run out of room, so before drawing the power node i extended the right branch to give me more room
do you have a sample code for this problem building an expression tree from infix?
Thanks Dr that helped alot
thank you your video help me this part was self study
can u tell how will the expression tree for the expression -a*(b-c)/d+e%f look like?
Like this, Unary minus is highest precedence, Mod is same as mult and divide
drive.google.com/file/d/1tJvsiBRG3e-AylK179iXHhGIP2Wwp0dX/view?usp=sharing
nice explanation!
Thank you sir
Thank you sir! That helped...btw I love the British accent. :D
how about prefix?
thank you sir :)
You saved my ass. Thank you.
I know I'm late but, thanks a lot.
Thank you! :)
1:03 "Is everyone happy with that?" - no - the exponent should be done before since it has higher precedence than the plus and the minus in the brackets before that due to the brackets. Arbitrarily adding in brackets changes the meaning of the expression!
using that logic the exponent operator would be done before the assignment operator. It will be done before the minus but the plus comes before the minus which is at the same level of precedence and therefore left to right evaluation occurs. If you use a stack to convert the reverse polish you will get the same answer as the tree walk which is gfk+pds-^-=
But surely the assignment operator should be the last operator to be used right? I mean it's no good assigning when you've not calculated what it is you want to assign beforehand.
I've no idea how this left-to-right evaluation is supposed to work as all I can see as the order of that equation is:
1. d - s
2. p ^ (d - s)
3. f + k
4. (f + k) - (p ^ (d - s))
5. g = ((f + k) - (p ^ (d - s)))
Also, how does having the expression in Reverse Polish Notation help equate the answer? If anything it is harder as if you have multiple digit numbers in the expression, you've just lost the operators acting as delimiters between them so you can't tell if 398- is 39 - 8 or 3 - 98.
The assignment operator is the last operator executed. A compiler cannot process infix, so the expression has to be in reverse polish so the compiler can generate the machine code to calculate the expression, as the data is seen by the time the operation is needed
I finally managed to write a program to evaluate infix! It just recurse-calls its own expression parsing logic whenever it encounters an open bracket then when it reaches the corresponding close bracket, it has incremented the character index to that point and can exit the recursion.
His postfix expression is incorrect.....even his tree is not following operator precedence....
If tree construction followed operator precedence. Then the final postfix answer should be "g=f+R-p^d-s
you skipped the hardest part, how to add the brackets to an infix expression?
Hùng Doãn Phi
I didn't skip it, taught my students this but never bothered doing a video, but it's generally not asked in our specification.
It's not that hard anyway you just need to make sure you leave gaps as you go. Here's how to do it (taken from my notes on reverse polish)
Converting Postfix back to Infix to preserve precedence
=============================================
We can see that if we try to go from an expression tree back to Infix we lose the precedence overrides implicit in the tree. If we need to get back to the Infix expression we can use the Postfix form from the tree.
Here is the process:
1. Start at the first item in the Postfix string
2. If item is an operand right it down and leave a gap go to 4
3. If item is an operator write it down in the first available gap between operands and place parenthesis around the operands go to 4
4. Move to next item if it exists and go to 2
5. Remove last brackets placed then attempt to remove all brackets where precedence is not overwritten
Using the 3 examples shown we will take the postfix and generate the original Infix expressions, we will start a new line where we encounter an operator and add the parenthesis.
Ex1
Postfix: a b c * +
a b c
a (b * c)
(a + (b * c) )
a + (b * c) outside brackets not necessary
Infix: a + b * c other brackets not necessary as * is higher than +
Ex2
Postfix: a b + c *
a b
(a + b) c
((a + b) * c) outside brackets not necessary
Infix: (a + b) * c final brackets necessary as these override precedence between + and *
Ex3
Postfix: g h d + f e k + * - =
g h d
g (h + d) f e k
g (h + d) f (e + k)
g (h + d) (f * (e + k) )
g ( (h + d) - (f * (e + k) ) )
(g = ((h + d) - (f * (e + k) ) ) )
g = ((h + d) - (f * (e + k) ) ) outside brackets not necessary
g = (h + d) - (f * (e + k) ) outside brackets only surround right hand of assignment
g = h + d - (f * (e + k) ) brackets not necessary between + and - evaluate left to right
g = h + d - f * (e + k) brackets not necessary between * and - as * is already higher precedence
Infix: g = h + d - f * (e + k) final brackets override precedence between * and + so necessary
HurrayBanana wow I never thought you would mind answering my question. thank you, sir, but I think you misunderstand my question.
I meant you taught us how to create an expression tree from an infix that is helpful, but to do so we need an input expression which is already added brackets in a formatted way like: ((a+b)/c)+(d/e). But when we create a program, it is not only required the accuracy but also convenience for users. And normally, when inputting an expression, people will enter (a+b)/c+d/e instead of ((a+b)/c)+(d/e). So before building an expression tree, we need to adjust the input expression to the form we need.
My idea is to store the expression in an array of string (each element of the array will store an operator, an operand, or even a smaller expression which is already added brackets in the way we need). Then we will step by step combine 2 small expressions and an operand between them to bigger expression:
A, B, and + become (A+B) // 3 elements become 1 element
C, D, and * become (C*D) // 3 elements become 1 element
(A+B), (C*D), and / became ((A+B)/(C*D)) // 3 elements become 1 element
...
At last we get the first element of the array as the string of the expression we need
I think my solution is quite complex, hope you can give me a better way to do this. Sorry for my bad English!
Hùng Doãn Phi
No problems but you don't need to add extra brackets
taking your example ( I've mentioned which symbol i am parsing as the font spacing is not predictable)
(a+b)/c+d/e
just use the stack to convert
parse Item 1 (
============
(a+b)/c+d/e
^
| |
| |
| |
-------
stack empty so push ( on stack
rpn currently empty
| |
| ( |
-------
stack
parse Item 2 a
============
(a+b)/c+d/e
^
write down a
rpn currently a
| |
| ( |
-------
stack
parse Item 3 +
============
(a+b)/c+d/e
^
higher precedence than ( so push on stack
rpn currently a
| |
| + |
| ( |
-------
stack
parse Item 4 b
============
(a+b)/c+d/e
^
write down b
rpn currently ab
| |
| + |
| ( |
-------
stack
parse Item 5 )
============
(a+b)/c+d/e
^
pop contents of stack up to ( and discard (
rpn currently ab+
| |
| |
| |
-------
stack - empty
parse Item 6 /
============
(a+b)/c+d/e
^
stack empty so push / on stack
rpn currently ab+
| |
| |
| / |
-------
stack
parse Item 7 c
============
(a+b)/c+d/e
^
write down c
rpn currently ab+c
| |
| |
| / |
-------
stack
parse Item 8 +
============
(a+b)/c+d/e
^
+ not higher precedence than what is on stack, so pop / from stack
stack now empty so push +
rpn currently ab+c/
| |
| |
| + |
-------
stack
parse Item 9 d
============
(a+b)/c+d/e
^
write down d
rpn currently ab+c/d
| |
| |
| + |
-------
stack
parse Item 10 /
============
(a+b)/c+d/e
^
/ higher precedence than top of stack so push
rpn currently ab+c/d
| |
| / |
| + |
-------
stack
parse Item 11 e
============
(a+b)/c+d/e
^
write down e
rpn currently ab+c/de
| |
| / |
| + |
-------
stack
Final step dump the stack
=========================
finished parsing input so pop entire contents of stack
rpn currently ab+c/de/
| |
| |
| + |
-------
stack
rpn currently ab+c/de/+
| |
| |
| |
-------
stack - empty
HurrayBanana Thanks a lot. I was thinking about how to get a postfix expression from the infix, but I could only do with the infix expression which doesn't contain brackets. Now I will try your solution. By the way, I think your lecture is easy to understand, you are very good at explaining to people, but you don't need to go too deep to the details, just give your students the way, and let them go by themselves
Varanasi
u da man xd
Oi!