Infix to Prefix conversion using Stacks Data Structure

hi everyone the topic that we are going to cover in this lecture is indexed to prefix conversion using stats that is how we convert an in-phase expression - you can say prefix expression using a stash there are other ways to perform the same operation but in this particular lecture we will target the use of stacks as our data structure so for that the first thing we need here is an expression so let us write an expression in order to convert it into the prefix notation so let's take an example of an expression a b + C a B a plus B multiplied by C minus T plus F let's say we have this in fix expression and we want to convert into the prefix expression so the first step for doing this or performing this conversion is we have to like rewards it ok reverse the given expression so by reversing the given expression what we get is f plus D minus C multiplied by B plus a that is exactly the flip version of the given expression which is a plus B multiplied by C minus D plus F like this after reversing this particular expression next thing you should do is before applying any logic or anything else just create a table directly go for creating a table okay so take what element should be record on the table or what should be the column of the table that is one is the practice that we will visit this expression tractor by character the second column will be of star that is what is the element or what is the particular character that we are going to put in this tag and the final one is our expression okay before going into detail you must remember that man mathematics rule stage power TV a multiplication addition and subtraction P demas which means that power has the crater's proceed and then Debian and then multiplication 10 addition and the subtraction is the the operator having their lowest or lowest or the minimum precedence as compared to these are the other operators over here okay now what we do is we start evaluating this expression that we have just reversed by collector bucket the way we'll split this string into collectors so first interval is same is F okay so whenever whenever this is rule that whenever you encounter an operand not operator not not anything from them you will directly place it in there it's your final expression not in this time only these operators will become the part of your finest stack okay so the next thing we have a next corrective encounter on from this equation is plus so plus will go directly to this tag and not to our final expression our expression will remain as it is then we encounter D collector please another operator operand not operator so the plus at the stack from this step will remain as it is and we will get get ft in the our expression so next up operator that we will get is minus so now in stock already half plus we encountered - so there's another rule that stairs if you have encounter a character having equal to or low precedence as compared to the topmost element of the stack then what you do is you will pop out all those operators having higher or equal precedence than the character you have encountered so here plus will pop out and minus will become the part of our stack okay gee I hope this is clear so next character that we have encountered is C so C will become the part of our final expression again we encounter which operator multiplication now you can see in stock we already have - so we have an operator which is of having unless precedence as compared to this one so it has no problem having a higher precedence operator on the top you can take it like this I will get the example of this thing as if you're if you are a student at any given particular University so there is always a faculty member assigned to a course to some students okay so they basically governs the class or teaches you in a way that's appropriate not not the other way around so you can think of it like this that the operator having higher precedence will always sit on the top if you encounter any connectors having low or equal precedence than the already existing operator on this task then the you can say you will basically pop out or do some operations accordingly so at this point we have class status of having high precision so as compared to this so this will pop up at this point - we have encountered operator that is having low precedence so multiplication will come on the top of - and our final expression will remain unseen so after multiplication we encounter an opening bracket so opening bracket will also become a part of your staff not your final expression so your expression will remain same then we have encountered B minus multiplication remains the same and B will become the part or you can say our expression then we encounter plus since you know we have opening bracket here so it has nothing to do with the elements out of place or put before this particular you can say bracket so we will insert or pushpop on this tag and our final expression ft plus CB will remain same then we have encountered another operand that is a which will become a part of our you can say final expression so this expression will become C B and E okay after a we have got a closing packet here so closing bracket will do what basically all the elements that are push into the stack till is corresponding opening bracket that is here you can see I am like boiling this particular opening bracket this is the corresponding opening bracket for this closing bracket that have encountered so all the operators that are placed after this opening bracket will be popped out so we have get plus C B a and plus in the output now you can see here that our expression has been routed there are no more characters in the given expression but we have caught two operators on this stack so we will pop them out one by one so our final expression will become FD plus c b a plus multiplication and then we are left with the minus here and the next step - will be power power so FD plus CP a plus multiplication and - now here we have received or we have formulated a and other expression as you can see here okay but this is not our final prefixed expression so in order to get prefix expression what we do is in order to convert into you can say prefix in mutation what we do is basically we will reverse this particular you can say this particular given expression of particular expression that we have encountered so far so by the word saying this our final expression will become minus multiplication plus a P C plus T and then that is exactly the you can say flipped version of the expression that we just have figured out so this expression that I have you can see highlighted in black box represents the prefix notation and this whole procedure is these procedure for conversion and for the conversion of any infix expression to prefix expression using stacks that's it for today's lecture thank you for watching if you like my video - give it a like and subscribe my channel

Channel: ComputerAdx

Views: 44,385

Keywords: Infix, Prefix, Stacks, Intfix to prefix, Conversion, Infix to prefix conversion, Infix notation, Prefix notation

Id: hFQlsyBl454

Length: 8min 42sec (522 seconds)

Published: Sat May 23 2020