building an expression tree from infix then walking it to produce postfix

[@villancikos]

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!

[@kamathprajna]

@Daniel Madden wow 😳😲

[@Farrukhw]

PostFix conversion starts at 5:40 ... Thanks for such a good explanation...

[@cakebakeproject]

👌

[@gautam1940]

Left Right Root! Left Right Root! Left Right Root! I just lost track with that .... This is a great explanation!!! Thank you

[@superkimsay]

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!

[@ryanjensen4232]

Wow, you're explanation/method was infinitely better than my CS professors. Thanks so much!

[@HurrayBanana]

Thanks

[@kamathprajna]

Simple yet effective explanation..don't know why my professor makes it complex Thank you

[@alfredoperez4436]

Thank you very much! only video that made sense

[@Kuro_Alalibo]

Brilliant illustration. Loved it

[@mohammaddcheema9417]

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 !

[@MegaGamervids]

You sir helped understand this easily. This is a great approach.

[@HurrayBanana]

no problem mate, that was the idea

[@Atma505]

Wish I had teachers like you, very nice and clear

[@GagandeepSingh-tl7zg]

That line technique was wonderful, i sorted out the rest myself i.e. preorder and inorder. Keep up the good work. Many thanks

[@KishanRaval00]

Oh my God. I didn't thought this approach.Thank you.

[@TVChinks]

u sir have helped me for this exam greatly u shall be be friend in the next life

[@HurrayBanana]

nice

[@OthmanAlikhan]

Really clear explanation and high video quality, thanks a lot =)

[@HurrayBanana]

+Othman Alikhan Happy to be of some help

[@Venuhmz]

this guy is awesome. i wish he was my teacher

[@feverdelrey]

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! :)

[@HurrayBanana]

+Fever Del Rey Thanks very much, hope I've helped a little bit cheers

[@Stxpz]

Much better than my A-Level teacher.

[@BharghaviGanesan]

very very useful sir.IT is mind blogging.

[@JakzAizzat]

Oh shit. This video totally helped me. Thanks man.

[@Arjun69]

Fantastic. 💕

[@w1ndro1d]

Excellent!

[@NehaKumari-yf9bh]

thank you sir !!!u really made it clear

[@danishajaib1923]

Simple and easy to understand. Thanks

[@HurrayBanana]

Cheers

[@iamdreamerdoer]

thanks. you made it look easy

[@perdio9359]

Holy that's so useful thanks.

[@ohm7163]

thanks for this video sir::

[@TechnoDB]

Can't we either convert infix to prefix or postfix first and then construct an expression tree from it with an easy algorithm?

[@HurrayBanana]

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

[@ankitaharwal5886]

i love it

[@غيداءابراهيم-ض9ح]

thank you your video help me this part was self study

[@dighechinmayt]

nice explanation!

[@wambateufack]

Thanks man

[@Mission.Control]

You saved my ass. Thank you.

[@UROMSTXY]

Thanks Dr that helped alot

[@ViddeshG]

Thank you sir! That helped...btw I love the British accent. :D

[@jirahroman2138]

do you have a sample code for this problem building an expression tree from infix?

[@zkfdsldfjsdjfl1]

Thank you sir

[@FamousEgyptboy]

thank you sir :)

[@rmp.attackerfake9446]

I know I'm late but, thanks a lot.

[@SuryaKosaraju]

Thank you! :)

[@VanBhardwaj]

And to change it to prefix we traverse it the same but mark the line to the left of each node? Does it work?

[@HurrayBanana]

Yep

[@SubhashSharma-mt5tp]

can u tell how will the expression tree for the expression -a*(b-c)/d+e%f look like?

[@HurrayBanana]

Like this, Unary minus is highest precedence, Mod is same as mult and divide drive.google.com/file/d/1tJvsiBRG3e-AylK179iXHhGIP2Wwp0dX/view?usp=sharing

[@sy69sempoi]

how about prefix?

[@mattarnold198]

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!

[@HurrayBanana]

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-^-=

[@mattarnold198]

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.

[@HurrayBanana]

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

[@mattarnold198]

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.

[@krrrm7313]

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?

[@HurrayBanana]

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

[@blessingadu9605]

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

[@hugjobk578]

you skipped the hardest part, how to add the brackets to an infix expression?

[@HurrayBanana]

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

[@hugjobk578]

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!

[@HurrayBanana]

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

[@hugjobk578]

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

[@pahalwanathiest]

Varanasi

[@subcentral5695]

u da man xd

[@Tadesan]

Oi!