3.8 infix to prefix using stack | Data structures

so in this lecture we are going to see how to convert infix expression into prefix expression in the previous video I have discussed the infix to postfix conversion using step now we will see the in fixed to prefix conversion using stack right see here also without stack you can convert from in fixed to prefix like we have discussed in the previous case see let us take this example I have same example I am taking that I have taken in the previous video right so here also you should know the precedence and associativity of the operators this is the prerequisite of this video okay right now we are going to follow those precedence and associativity rules first of all see check out the precedence of these operators which one is higher precedence this multiplication is having higher precedence right so first of all you need to solve this expression that is B into C see these are what operands this is what operator right now prefix expression means if this is B into C means these are operands this is what operator in prefix this operator should be before these or prints in postfix this operator should be after these operands pre means per la Poste means both me you can relate it with prepaid mobile and post paid mobile right and in fixed means this operator is in between these operands that is in fixed expression so this is what in fixed expression now this it is so this is higher so first of all you are you have to solve this one so prefix of this is what estwick B into C right now this says what one operand now we have plus this operator and this is what another operand this operand this open we have two operand and in between these open we have now plus this is what operator now we are going to solve for this one because I have left with only one operator now now for prefix this operator should be before these these operands a and second operand is this one means Asterix B si right so this is what you can say a prefix for the syntax right in this case also in first scan this will be solved in second sense scan again we will solve for this + right so this there are multiple scans to solve this problem without using staff now here in this case I am solving this this is a smaller expression if this is the expression then here multiple scans would be there may be 10 or maybe 20 15 I cannot say right now rather than scanning it multiple times because this process is you know very time-consuming process very lengthy process so we should follow a method in which we scan only once from here to here and after reaching at the end of this expression we will get our output you can say we will get our prefix expression we don't need to scan this expression multiple times right so that is that would be what efficient algorithm so that is possible using stamp that is why here I will discuss with you conversion of in fixed to prefix we using stack we will also discuss to tell you our answer we will also discuss how you can convert this expression without using step at last first of all I will convert this after that I will write down all the rules here only so now this conversion is also same almost same as the infix to postfix conversion but the difference is what first of all you need to reverse this in fixed conversion if you are converting this input prefix in that case only right so first of all reverse this one means we will start writing from here so here we have Q so here you write Q then after that plus T multiplication we then divide then you then divide then W then again multiplication now this is what closing parenthesis so here also I am writing closing parenthesis right now this is what the reverse of this in fixed expression now somewhere it is written that here in the in fixed in the reverse of the same fix convert sorry reverse these parentheses also if this is closing parentheses in the in fix here write down it as opening and here write down it as closing like this but here I'm not going to follow that process right that is also fine you can do something like this after that convert this into postfix and after that reverse that postfix expression but I am NOT going to do this I'm going to follow the second approach right this is now our reverse in fix expression now see same we are going to take one step if operator that will be found then we are using stack for pushing those operators and if operand is there then directly we are going to print those up cooperates right now now scan this reverse in fix expression from left to right you can scan it from right to left also and after that also you can get the prefix expression so there are many ways to or three ways to convert infix to prefix right this is one of all the possible ways right now here we have Q so we are not going to push anything into the stack if operand is there directly print it fine next plus this is what operator now see is there anything in the step no directly push it now we have Q in this prefix expression only now we have P nothing to push in the staff directly right down here print it right now we have a strict operator or multiplication operator you can say now check if in staff I have plus of the stat is this one now we are going to check the precedence see now the if the incoming operator is having higher precedence then the top of the step then what you will do simply push this operator here means plus into and here we have Q P now next is V so no need to write down anything in the staff directly write down this one here next is divine now see check out the top of the stack is multiplication right and precedence of this and this divide and multiply having same precedence in that case check out the associativity now associativity of this is what left to right so if associativity is left to right then simply push the incoming operator into the strength right but that is not a case in infix to postfix conversion in that case if associativity is left to right then pop out this one right and again check the incoming operator with the new top of the stack but here the rule is different because we are converting in fixed to prefix now right so now here we have Q T and V now we have u means simply write down here V you now again we have divided check out the top of the stack is having divided same precedence operator is there incoming operator is the same precedence of this operator now check out the society row little left to right in that case simply push it right and here I have Q tu ba u now next is after this one I have W now stack would be as a tease and here we will append this W right now asterisk now check out again same precedence associativity is also left to right no need to pop out no need to do anything simply push it into the stack right now after this see now I have closing parenthesis now in this case if you find any closing parenthesis simply put that parenthesis into the strength right in previous case in fixed to postfix what we have done if opening parenthesis is there then push it into the stack if closing parenthesis is there then pop out the stack one by one right till you reach till you find the opening parenthesis corresponding to that closing parenthesis but here the rule is different reverse now simply push it into the stack right now here we have now after this we have P no need to do anything sin we append this P here next is exponential now see here we have closing parentheses right so if any operator comes after this closing parenthesis simply push that into the stack no need to check out any parent any precedence right now simply push it after this we have au now directly you will write o here and the stack would be unaffected right after ona I have what opening parenthesis now in this case if you find any opening parenthesis if the that the next symbol is opening parenthesis then what you will do then from the stack pop out all the operators one by one right till you find the closing parenthesis corresponding to this opening parenthesis right here the rule is reverse now see we have top of the stack is having exponent so first of all pop out this one right next is what now we find closing parenthesis now stop no need to pop out anything right and no need to write down these parenthesis into the stack now the remaining stake is plus hystrix divided divided and history now after this we have plus so now next symbol is plus right now check out the top of the stack is Astrix and this you can say your multiplication this is having higher precedence and the incoming operator is having lower precedence then the operator which is at the top of the step then you cannot push it here first of all pop out this top of the stack right then again check this one with the new top of the stack now once you pop out this one and you will append this or you can say you can print it now after this one so now the prefix would be the prefix expression would be no multiplication we have formed out now in the staff in the stack I have if this is the incoming operator plus now again check the new talk of the snake is this one now again check the prefer the precedence still this is incoming operator is having lower precedence in the top of the stack so you cannot push it again pop right now we will pop out this one like this right now new top of the stack is this one again check but still the same precedence of this is higher so you cannot put here the plus again pop out of this one now check out with this one same plus is having lower precedence than the top of the stick then pop out this one also now in the stack I have plus now check out the precedence these are having same precedence now check out the associativity associativity is what left to right if left to right then no need to pop out this thing simply push the incoming operator now we have two plus in the step right now after this plus I have n so stack would be unaffected and here we will append this afternoon we have again is trick now this is humming multiplication is having higher precedence then the top of the stack right if higher precedence then you can simply push it and this expression would be same now after this one I have M so this is what operand no need to push anything in the step simply will append this into this expression now we have - now check out this one with the top of the stacks now here we have multiplication so now this incoming operator is having lower precedence than the top of the stack so you cannot push it what you need to do first of all pop out this thing this operator right so here we have now this one now in this trap I have plus and plus but again this is the new top of the stack again check out with this one now plus and minuses having same precedence check out the society that is left to right if left to right simply push this operator here the incoming operator into the staff now after that I have a so now this is operand simply append this one here after this I have plus now check out with this one here we have - both are having same precedence check out the society left to right simply if left to right simply push it now next is okay so in the stack I have this one and directly you will write down K here now you have reached till end of this expression now what you will do check out the strap and pop the stack pop out the operators from the stack till the stack becomes empty right now first of all pop out this plus now I am writing this here plus 4 pound this one after that minus then plus then plus right now stack is empty now stop so now see this is not done yet right now what you need to do you have to reverse this expression right so for reversing what you will do scan this from right to left plus and write down from here plus plus minus plus now this is the final prefix expression for this post the desam fixed expression now this is the conversion using stack now we will discuss conversion without stack right and we will compare our answer with this one whether we are getting getting the same answer or not fine see so now this has a given in fixed expression no need to convert it into that reverse and fix expression you need to reverse it say simply scan this one right and find out which operator is having higher precedence highest precedence so we know the parenthesis are having higher precedence right out of all the operator present here so fine so first of all solve this one convert this into prefix what should be the prefix here the sub operator should be before these operands so this this is not a prefix of this one so this is now one operand this complete will act as a oprand now next although this this is the operator which is having second highest but this thing we have already solved because this is within these parentheses this operator all right so now after this we have this multiplication and divide these are having higher precedence so now here both multiplication and divide both are having same precedence so check out the society were associating associativity is left to right now left to right means we will start scanning from left and this is the first multiplication so first of all you need to solve this one right so for this one for this operator you can see our parents are this one and this one so convert it into prefix first of all so for this one prefix is in second skin in first skin we have done this thing in second skin this would be MN now this is what complete operand 1 opened right now stand this one from left to right because these are having left to right associativity right now another is this one fine so now you need to solve this one for this operator for prints are what see one operand is this one W another apprentice this one means after solving this one we have got this operand right so now one operand is this one one operand is this one right now how to convert this you can say this is something like this this is one operand this is another operand and this is what operator so the prefix of this one is Astrix then this operand opie then W this would be the case right so now here what you can write this one here you will write asterisk this is the operand and here you will write W right so this is not the complete operand so this is now complete or print roughly I am doing this thing I am NOT writing each for each scan right so that would be very lengthy now next is now after this one this from left to right this is the operator that is this divide we will solve this division right for this degrees in the operators sorry the operands are one is U and one operand is this complete operand right because after solving this this we have got so this is something like you can say write like this w and here we have this operator and here we have you so this is one operand this is another operant this is operator so for doing the prefix of this one you will do what this operator should be before these operands right so this is something like this here I hope you are getting this so this is now a complete operand so how you can write it right on this thing here here you will write down the wide and W and Q so now this is a complete orbit right this is another operator now next next is this one from left to right next we will find we have found this division operator for this division the operator the operands are one is we and one is this complete right so now this after this divide after this we write this is one operand this is another so have you will convert this into prefix simply put this operator before these opens means here you will put before this operand and here we will write tweak so now this is what a complete footprint and here we have hystrix him and this is another operand right now after this we have this multiplication operator right so now for this operator operands are one is T right and one is this complete operand so here you can say here we have Astrix and a way of T so when is this operand one is this one so put this operator before these operands to get a prefix for this expression so now here you will write istrict and here you write T so now this is this is a complete operand right now we are done we have solved all the multiplication and divide operators here now next precedence is of plus and minus but with a here we have multiple plus and minus so which one you will solve first same check the associativity associativity is left to right so scan this from left to right right stamp while scan you will get we are getting this plus first so you will solve this one first right so now for this Plus this is open this is the open one and two two opens are there so four prefix you will write here plus before this K and N and this is what a complete open now this is what another you can sell better we have found that is - no so now you will solve this - for this - now see for this - the operands are one is this complete and one is this one that is because this I have already converted into prefix that is this one so here you can say here we have - right for this - this is one operand this is another operand so you simply put this - before these operands so now this is what complete operand right now here now we have this + so solve this one for this plus C one operand is we have solved this one one operand is this complete right this complete for this plus and second is what second is what is this one up to P because we have solved till t plus we haven't solved right so now you can visualize it something like this this is one operand here after this we have plus and this has another oprand till P so how you will convert this put this plus before these operands so here we will write class right and after that these operands now we are left with this plus so here you can say this + n cube for this plus one operand is this complete right this complete from here to here and one is Q how will convert it into graphics simply put this plus before both the operands that is + you will write here and here simply will write Q so this is now the prefix expression for this inference without using stack and now we can compare this with this when I guess both are same so I guess you have analyzed now that for getting this prefix from this in fix expression using this approach without using stack you need to or you can see the compiler need to scan this infix expression multiple times it's not like that in one scan only you can get this prefix as I guess you have analyzed here but in when you are using stack in that case compiler need to scan only once this expression from left to right right so now it's up to you which approach you're going to follow so now I guess no need to write down the rules here because if you get it how to convert this into this you can write down the steps because obviously I am going to write down the steps only and if you know how to convert it right so you can easily write down those steps first of all reverse this infix expression right then scan it from left to right if operand is there simply printed if operator is there then what you will check out the stack if stack is empty or in the stack we have closing parenthesis right then simply push the dot operator into the stack right if that is not the case if spec is not empty then check out the precedence of the incoming operator if the precedence of incoming operator is higher than the precedence of the top of the stack then simply push the incoming operator into the stack right but second another rule is what if the precedence of incoming operator is less then the operator which is present at the top of the step then what we will do pop from the stack and print it again check the incoming operator with the new top of the stack right and if presidents of both operator the incoming operator and the top of the stack operator is same then check out the associativity rule right if associativity is left to right simply push the incoming operator into the stack if associativity is right to left then first of all pop from the strap and then again check the incoming operator with the new top of the stack right something like this I guess you can easily write down these rules no need to write on these rules here and after that yes one more thing is important point is what after getting this thing you need to reverse this expression also now this is the final your you can say that prefix expression fine so now next video and discuss with you about binary search trees right cells in the next video tell them of why I take

Channel: Jenny's lectures CS/IT NET&JRF

Views: 329,031

Keywords: data structure tutorials, data structure and algorithms, how to convert infix to prefix with example, infix to prefix using stack, infix to prefix without stack, what is stack in data structure, infix prefix and postfix expression in data structure, infix to prefix conversion using stack, infix to prefix and postfix conversion, ugc net computer science tutorials, gate computer science lectures, jennys lectures, jenny data structures, jenny's lectures cs/it NET&JRF

Id: 8QxlrRws9OI

Length: 24min 5sec (1445 seconds)

Published: Fri Oct 11 2019