3.9 Evaluation of Prefix and Postfix expressions using stack | Data structures

in this lecture we are going to talk about the evaluation of prefix and postfix expressions see I have already uploaded a video an evaluation of postfix expression in that video I have discussed evaluation of postfix expression using stack right in this video I'll discuss both method without using stack as well as using stack how you can evaluate prefix and postfix expressions right now see I'm taking suppose this as our in fixed expression now you have to I'm going to convert it into prefix expression that thing also I have discussed in the previous video how to convert infix to prefix so you can check out that video in this I button right I'm directly right writing this the prefix form of the same fix expression right and here the values of this these variables are I have written here fine now see the prefix expression for this in fix expression would be what so now this is what the prefix notation of the sin fix and I have here substituted the value of these variables right so now this is a prefix expression and now you have to evaluate this one you need to find out a value for this one see what is prefix in fix and postfix expression that thing also I have discussed in the previous video one of the previous video so you can check out that video in this I button prefix means how you denote the prefix notation first of all you will write cooperator then brain and here again operate right this is operator this is one operand this is another operand see here we are discussing specifically about binary operators binary operator means exactly they needs two operands fine now the first step to evaluate this expression is what without step I am going to discuss first write scan this expression from right to left in case of prefix we scan it from right to left and in case of postfix we scan the expression from left to right right now scan it from right to left and find out the first operator so while scanning the first operator is this one after this operator find out the two operand immediately next to this operand so after this operand first after this operator first operand is 2 another apprentice three it means we first but you can say you have to find out this pattern operator and operand and operand right once you find out this pattern you can evaluate that thing fine so while scanning first operator is this one find out just after this operator the two operand when is this one one is this one so for this operator you can say these are two operands fine so this is a in sorry prefix expression right you can say within this perfect one prefix is this one so first of all evaluate this one now how do I evaluate this one see for this for this see this the first operand how you write the first operand then the operator and then the second operand means in in fixed form it this prefix means this 1 2 raised to power 3 this is power 2 raised to power 3 means 8 right so here what you will write down it after evaluation this would become 8 so now the expression is something like this fine for this I have written 8 right I have even better this one now again find again scan from right to left and find out the first operator so while scanning from right to left now the first operator is thus divided fine now if you are this prefix expression is valid then definitely you will get 2 operand after this maybe 2 or 3 3 4 more operands can be there but you need to find out next to immediate next 2 suppose here 1 & 2 is also there or you can say 2 & 3 are also there but for this how you are going to evaluate this one for this operator the operand would be this one and this one just immediate next - we are not will not consider that these 1 right so here now for this case this is first for this operator this is one operand this is another operand so now how you can write this thing Steen / a now the value of this one is 16 divided by 8 8 is what - so now the expression would become this 1 3 4 and for this one you can write down value 2 now another scan in another scan you find out from right to left this is the first operator now for this operator see our prayers are two operands are the next two immediate in x2 means this one and this one we will not consider to this thing you need to take care fine now here this is our prefix 1 a strict 3 and 4 now for this one to evaluate this one this is actually 3 into 4 means first operand then operator you will put then 4 means here you will write 2 n so now the your expression would become 2 here we have 2 N and here again we have two right now another scan the first from right to left the first operator is + now find out the immediate next two operands one is to one is 12 right so for this one this is our now prefix so how to evaluate this 1 2 + 2 l first operand then this operator then this 2 L means it becomes 14 so then now the expression is this operator then 14 then to see if your expression this prefix expression is not valid in that case you will not find maybe sometimes you will not find two operands after operator if this is the case then you can say your expression is not valid right now here this is the operator this is first operand this is another operand so now it means 14 minus 2 that is 2 n so now the answer is 12 without stat you have evaluated this prefix expression but in this case the problem is what you are you have to scan this expression multiple times in one scan I got this value that is that 8th value in another scan for this divide you how evaluated another scan then another scan something like this fine so this is you can say time-consuming process now another thing is I want in one scan only I want to evaluate the expression I need to scan only once this expression from right to left and I get the value 12 now that thing you can do with stack now how you will evaluate this prefix expression using stack that thing we'll discuss now so now this is the stack I have taken fine you have to create a stack right now first step is start scanning the prefix expression from right to left and now if you found you find the operand then simply push that operand into the stack right so now see start scanning first of all we have three this is operand simply push it into the stack again - this is also operand simply push it into the stack next is what operator now you need to do what now you need to pop out two operands from the step 2 values from the stack means top of the stack and next element to the top also - element you need to pop out so now first of all pop out this - so you can say in operand 1 I have 2 and next three in operand 2 I have 3 only two operand you need to pop out if this time only to open we have but suppose here five four friends are there in that case also the top element and next to the top element these two operand you need to pop out just two elements right now see how you will evaluate now you can do operand 1 then the operator you find means here operator and here operand 2 operand 1 is 2 operator is this one and operand 2 is 3 so when word this one the value is this is power so 2 raised to power 3 means 8 right and after evaluation this value you need to push this value into the stack right so we have bombed out this one this one and now we have pushed 8 here fine now after that after this we have 16 this is operand simply push it after this we have a gain operator right so now what a little pop out to operands the top and the next stop now now see in the Copeland 1 I have 16 in operand 2 I have it right now how to do 16 operator is divided and 8 this thing operate happened 1 operator and operand 2 now the value is 2 and push this value into the stack so now we have popped out this one also this one also simply push this 2 here now in stock I have only one element next is 4 this is operand push it into the stack next is 3 this is operand push it into the stack next is s tricks or you can say multiplication right now pop out the two operand now in this case C operand 1 is 3 means this you need to pop out then next operand 2 is 4 3 we have popped out for we have popped out right this is now the top of the step right how we are going to perform push and pop operation that time also we have discussed I have already discussed what is stack and data structure in detail you can check out the playlist fine now see the operator is this one so 3 into 4 that is 12 simply push this to n the result into the stack that is here we push to n after this we have 2 this is operand simply push it into the stack after this we have plus this is what operator now you need to do what push to a print first operand would be 2 second operand would be 2 n now operator is plus so what you need to do 2 plus 2 n you will read this one that is 14 and push this result into the string that is 14 after this we have - this is also operator no need to push anything now pop out the two operands from the strap now operand 1 is 14 operand 2 is to write and perform this one that is 14 minus 2 that is 2n and push this to L into the step right now see we are reached to the end of the expression but now there is nothing now in this case at this point of time if there is only one value in the stack means that is valid prefix expression and you have evaluated that prefix expression correctly now seeing the step I have only one value one element so simply return this value right on the top of the stack because at this time this is the top of the stack so now the answer would be 2n right and now the stack becomes empty as you can see using stack also we have found the same answer right so you can use stack also you can evaluate this one without stack also but in this case the compiler need to scan the expression only once right and in that case without stack the compiler need to scan the expression multiple times right so that is time-consuming process but manually you can evaluate this without using stack programmatically when you evaluate this thing then we use stack so now the algorithm for this thing is C so this is the algorithm first step is scan the prefix expression from right to left right you can write down here a for loop that is for I is equal to from length minus 1 to 0 till then you are going to scan that expression fine for each character in the prefix expression what you need to do in a loop you will write if operand is there what we have done simply push it onto the stack if operator is there in that case pop two elements operand operator so to the operand one is top element operand 2 is the next two top elements fine and now what we will do operand 1 operator operand 2 and you will store this result into a variable any variable you can take here I'm taking result and push this result on to the stack right and you are going to repeat these steps fine because this we are going to write down in a loop from length minus 1 to 0 once the I value becomes 0 simply you will return the stack top this is it this is the algorithm now we will see manually how you will evaluate a postfix expression right we have already discussed using stack how you can evaluate that thing the same example I am taking this is the example this is the postfix expression for this in fix expression how to convert infix to postfix that camel try your disgust you can check out that video in this I button right after conversion this is the postfix expression and after substituting the value for these variable now this is a postfix expression now you have to find out the value of this one you have to evaluate this one now postfix means the that pattern would be operand operand and here operator binary operator I'm talking about means operand opened and after that operator for this operator these two are the operands right now in this case you need to scan it from left to right almost same algorithm we have evaluation of prefix and postfix this is what evaluation of postfix I am discussing here right now see scan it from left to right and find out the first operator as soon as you find out the first operator that is we have found s trick here without step I am discussing here right now you need to find out this pattern find out the two preceding operand for this operator to proceeding right it doesn't mean that here we have three operands so you can take two or three no immediate previous to open you need to find out this pattern you need to find out operator so this is the operator this is one operand this is another option you can say why so now here you can say obtain one we have three and operand 2 we have four right now this case means 3 into 4 this is actually something like this you need to evaluate this one 3 into 4 that is 12 so you have to substitute here to L means now the expression would be 2 here we have 2 L then plus then 16 then 2 3 this one then divide and then - right again in the next scan the first operator you find is + now find out this pattern if the expression is valid then everywhere you will find out this pattern till you get 1 now see before this plus one operand is this one one is this one it means this is the expression now postfix expression so it means here we have 2 plus 2 L 2 plus 12 means 14 here you lied 14 here we have 16 2 3 this this and this this is the expression now now another skin again compiler will scan this end the first operator is this one now for this operator immediate previous two operands one is this one one is this one means this one now it means to raise to power 3 to raise power 3 means 8 so now the expression would be 1416 here you will write 8 divided and - again in another skin the first operator you find is this 1 for this operator this is the operand this is the operand operand operand one is this one open 2 is this one now it means 16 divided by 8 means to here you will write 14 - and - now in another skin the first operator is - now for this operator find out the previous two operands immediate previous one is this one one is this one right now 14 and 2 it means 14 minus 2 that is 12 and now we got 12 answer is same because we are we are taking the same expression right so now this is how you can evaluate the postfix expression without using stack if stack you use that is also a very simple see briefly I am talking about from left to right start scanning if our friend you will find push it into the stack means here we have to simply push it into the stack next is 3 simply push it into the stack next is 4 simply push it into the stack next is multiplication now you need to pop out two elements from the stack right but here the slight difference from the evaluation of prefixes what here when you pop out this 4 it means it is operand 2 not operand 1 the next element is operand 1 that is 3 so actually you are going to do what now we are going to do or and one here the operator and operand to write but in that case you remember when you pop out this thing then this would be operator one and this would be sorry this would be operand 1 this would be operand 2 but here the thing are different slight differences this thing only this would be copper end to this one and this would be operand 1 just reverse right means here 3 into 4 operator is this one 3 into 4 and here also here also same thing we have done that is to L see in multiplication there would be no problem if you write 4 into 3 or 3 into 4 but in case of divide it would create a problem so you need to take care of these rules in case of - also it would create a problem now see simply push this result here means 2 L so simply push this 12 here now next is Plus this is also operator so pop out two operand so here in this case now operand 2 is what - well operand 1 is what - so now operand 1 that is - operator is plus and here we have 2 L means 14 so here I have written what 14 by now C so simply push this 14 here because we have got out of these two now we have 14 here 16 simply push the 16 here next we have to simply push this if operator operand is there simply push that next is 3 this is also apparent simply push it now next is exponent now pop out - operand - element from the step here operand - would be 3 and operand 1 would be 2 so now we append 1 operator operand 2 means 2 operator is this 1 2 raise to power 3 that is 8 and simply push that result into the step means we have popped out 3 and 2 and now it you are going to push next is divide same pop out two operand from here so now in this case operand 2 would be 8 and one would be 60 we have popped out these things now put out put here opened one is 16 16 operators divided it is eights / is for a 16 / ready it is to push that result here next is - pop out this one again - opened from the stack now opened 2 is 2 and operand 1 is 14 now here simply push operand 1 is 14 operator is - here we have 2 and simply push that here now we have reached till the end of the expression now if in the stack I have only one value and here you can see here will be how only one value now return the top of the stack that is - well you are going to return means the result is 12 and we have formed the same result so I guess algorithm you can easily write down or four algorithm you can check out this video in the side button see we can also represent this in fixed expression into a tree form binary tree form how we are going to represent this thing into a tree form how you can create that expression tree that thing we will discuss in the next video so I'll see you in the next video - the number why take it

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

Views: 144,480

Keywords: data structure tutorials, operating system, data structure and algorithms, how to evaluate prefix and postfix expressions using stack, prefix expression evaluation, postfix evaluation using stack, what are infix prefix and postfix expressions, what is stack in data structure, evaluation of postfix and prefix using stack, jennys lectures, jenny data structures, jenny's lectures cs/it NET&JRF, jayanti khatri lamba, ugc net computer science tutorials, gate computer science lectures

Id: o6vj5l_W2h8

Length: 21min 3sec (1263 seconds)

Published: Mon Oct 14 2019