3.4 Infix Prefix and Postfix expressions | Data structures

in this lecture we are going to talk about what is in fixed prefix and postfix expressions as well as how to evaluate these expressions see the evaluation of these expressions are you can say it's an important application of stack right so now first of all what is an expression see expression is basically you can say it it contains constraints may be variables or some symbols operators parentheses something like this right now see if I write something like this 5 plus 1 this is what an expression because it is containing constant plus this is what a symbol or you can say operator right if I write P plus Q this is also an expression and if I write a plus 5 this is also an expression right here generally we write down expression in this form see first of all we will be right what operand here we will write operator and here you will write again operand here in this video specifically I am talking about binary operators right binary operator means binary operator exactly needs two operands right there are some operators which needs only one operand also some operators needs three operands but here I am talking about binary operators it is going to take to open one is this one one is this one right this point is very important right now this operand here in this case Co operand is what a this is what operator and this is what another operand but it is not compulsory that this expression sorry this operand is a simple operand or you can say simple constant or variable it itself may be a expression right see now if I write something like this a minus one and here i am writing plus five so this is also an expression now here for this five one operand is sorry for this operator plus one is one operand is five another operand is this one this complete expression is in operand right and within this operator also this is operator and for this operator this is one open this is another operator right so this power plant itself may be a expression C generally we write our expression in the in this form only right you can say operand then operator then operand again right operator is between operands right so this form is known as in fixed expression this representation of expression is known as this is known as in fix expression right or in fix notation you can say now how do you when weight these expressions see expression I have told you it is what it is a combination of you can take constants variables and some symbols which are arranged according to some rules some grammar rules right and we parse these expressions according to the rules on right now these are simple expression see you can say how to evaluate this 1 5 plus 1 is what 6 suppose I am taking a complex expression in that case what you will do see suppose I am taking 5 plus 1 into 6 this is the expression this is the in fixed expression right now how to evaluate this thing see the output can be may be you can evaluate something like this 5 plus 1 is 6 6 into 6 that is 36 another case may be first of all you evaluate this one means 5 plus 6 into 1 is 6 and the answer is 11 now out of B is 2 output which one is correct right because obviously only one would be correct so you need to evaluate this expression we need to process this we need to parse it according to the rules now what are those rules evaluation of in fixed expression is following some precedence and associativity rules so you should know the precedence and associativity of the operators right that is very important see generally we use parenthesis or plus minus or divide or a multiplication so I am going to tell that residence of these operators the complete precedence of all the operators and associativity with associativity I'll discuss in a separate video so the precedence chart is what first is what having this parenthesis are having higher precedence or you can say highest precedence then we have exponential or you can say power next is multiplication and divide and next is plus n minus right now first second precedence third or you can say priority of these operators plus associate associativity is this is having right-to-left this is having left to right and this is having left to right where you are going to use these associativity I'm going to tell you that thing also now see to evaluate this expression check out the precedence of the operators two operators we have precedence of Straker you can see a multiplication is higher than this plus so first of all you need to evaluate this one right means 6 into 1 for this operator we are talking about binary operator so one operand is this one one oprand would be this one right so this is something like this you can say 6 into 1 so now that is 6 now 5 plus 6 is what 11 so this should be the correct answer this is how we are going to be going to evaluate this expression now if you want to evaluate this 5 plus 1 first rather than this multiplication right although this is having higher precedence but you want to evaluate 5 plus 1 first right so you can write something like this now parenthesis is having higher precedence than this district so now the answer would be what 5 plus 1 is 6 6 into 6 is 36 in this case answer is this one correct answer is this one right so these rules are very important now here suppose I am taking one more complex expression something like this now for this expression how we are going to evaluate this in fix expression same we are going to follow the precedence and associativity rules right check out the precedence of these operators now here in this case see this multiplication and divide both are having same precedence so now the problem is in which one you are going to evaluate first so now in this case to resolve this conflict you need to check the sociate ility right associativity of these operators are left to right it means you are going to scan this from left right from left to right you are going to move and whichever operator you will find first you are going to evaluate that thing first that operator first right so while going from left to right this s trick this multiplication is first rather than this divided so you are going to evaluate this one first so now 1 plus n plus 30 divided by 5 now in this you are going to evaluate this one because this is having higher precedence so now 1 plus 10 plus 6 now again I have two operators plus and plus both are having same precedence so which you are going to evaluate first although the answer will be same if you evaluate this one first or this one first but you should follow the rules right and rules are check out the society that is that is left to right so first of all left to right means this plus we are going to evaluate first means 11 plus 6 so now the answer will be 17 now take another example where the sauce activity would be right-to-left see I'm taking this example so now to evaluate this expression check out the precedence of the operators two operators have having that is same precedence so check out the associativity that is a right to left right so in this case you are going to scan this from right so first is this one so first we are going to evaluate this one this is what a power operator so 2 raised to power 3 is what it should be 8 and now 2 raised to power 8 I guess this should be 256 you check out this thing again if see this is the right answer but if you evaluate from this one then answer would be 2 raised to power 2 that is 4 4 raised to power 3 that is 64 so that is not the correct answer then that is why when you are evaluating an infix expression you need to take care of some extra rules that is precedence and associativity rules of the operators right and what you can say you can write this in fix expression with the help of parentheses if parentheses are there then you can say no need to check out the precedence and associativity rules right like suppose if you are writing then I guess you can easily evaluate this one right so now you can say that the passing of this in fixed expression or you can say processing off in fix expression is difficult right and it is also costly in terms of time as well as in terms of you can say that memory consumption right so now here we have two more expressions one is prefix and another is postfix expression there in that case you don't need any extra information to evaluate those expressions like precedence for associativity rules fine how to evaluate these expression that thing also we will discuss with example in next video first of all in this video we will see what are those expressions see prefix this is also known as you can say polish notation so how to represent this expression see in this case here you will write first of all operator would be there then our print and operand two operands would be there and before these operands we have operator that is prefix means specially right now see if this is what are in fixed expression that is five plus one then for this the prefix expression would be this operator would be before these operands that is five and one now this is what prefix expression corresponding to this infix expression now here also it is not compulsory that these operands would be a constant or some variable simple constant or variable these operands may be a complex expression itself right like in this case we have discussed fine C let us take one example suppose I am taking this example a into B plus C this is an fix expression of how you will write this into prefix expression C check out the precedence of this this thing I guess I disgust you can check out that video in the cyber and how to convert infix to graphics so first of all you will convert this one that is Asterix a B right plus C now this is one open this is another open now for this operator these are two operands here you write plus a B and C so this is what the prefix corresponding to the same fixed expression right and while you evaluate this expression you don't need any extra information you don't need any precedence or associativity rule how you will convert it sorry how you will evaluate this that thing we'll discuss in next video fine now what about postfix expression it is also known as reverse polish notation right now in postfix expression you will represent it something like this a print print and here you will have operator fine operator would be after these operands if you have five plus one then corresponding to this the postfix expression would be this operator would be after or prints that is five one and plus how we convert this infix to postfix that also I have discussed you can check out that video in this I button right now in this case also these operands may be a complex expression itself it is not compulsory that these are simple constant or variables same example you can take this one only into B plus C now to convert this into postfix right have to convert first of all will convert this one abs tricks right then we have plus and C so for this plus this is one operand this is another operand so now for this this postfix would be this operator would be after these operands that is C and plus now this is what the post fix expression for this in fix expression right and interesting point here also for evaluating this post fix or reverse polish notation you don't need any extra information or any you can say precedence or associativity rule something like this right so the parsing of this post fix and Fix expressions are simple as compared to in fix expression right you can say in terms of memory also memory consumption is also less and time taken is also less so you can say a computer can easily read these expression prefix and postfix and can parse these expression easily but a human being can easily read in fix expression something like this right and can understand these expression more easy rather than prefix and postfix for computer purpose these expression are good for us these type of expressions are good so see here you can say these three are different through different and you can say equivalent ways to write expressions fine so now in next video we will discuss how to evaluate prefix and postfix expression with example fine so I'll so in the next video is in BA BA retake

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

Views: 377,269

Keywords: data structure tutorials, data structure and algorithms, infix prefix postfix expressions in data structure, infix to prefix conversion, infix to postfix conversion, what are infix prefix and postfix notations, jennys lectures, jenny data structures, jenny's lecture cs/it NET&JRF, ugc net computer science tutorials, gate computer science study material, jayanti khatri lamba, c programming tutorials, data structure notes, what is stack in data structure, operating system

Id: RY4GkLahbCI

Length: 14min 14sec (854 seconds)

Published: Sat Oct 12 2019