Hi, everyone.
So today we are going to solve this problem, evaluate expression.
OK, so the problem statement is very simple.
So this is basically that prop string.
So this is a very interesting so this will be our input and we have to evaluate our postfix notation.
OK, so there are basically two types of annotations.
So we have three notations.
So these notations are infix.
We have postfix.
And we have prefix notation.
OK, so generally we are only aware of infix notation, so infix means basically two plus one.
Multiple-entry, so this is an example of infix notation.
OK, but there are postfix and prefix notation.
So what happens?
So if you will give this input to the calculator, so, for example, if you will give this input to
the calculator, then how the calculator will evaluate our answer.
So first of all, Calculator will convert this infix expression into postfix and then postfix expression
is evaluated and then we will get our answer.
OK, so that's how the calculator works.
So Calculator, the working of calculator is very simple.
First of all, the first step is to convert the infix expression into the postfix.
And then evaluate the postfix expression.
OK, so evaluate postfix expression so they'll tell the calculator works.
So basically we are given postfix expression.
So this is a postfix.
Expression and we have to evaluate this, OK, so we have to evaluate this.
So the other name of this question can be evaluated, postfix expression.
The other name of postfix expression is also called reverse Polish notation.
OK, so reverse Polish notation.
This is the name of Postfix.
OK, so basically how we can convert infix to postfix.
So this is very simple.
OK, so this is given postfix expression and this is basically its corresponding infix.
So this is infix and this we already know.
Similarly, this is infix and we are very familiar with the infix views and fixing our day to day life
so how we can convert infix into postfix.
OK, so for example, let us consider infix expression, so let us consider this one only.
So let's take it today.
OK, so this is a very good example.
So this is infix.
Now, how we can convert infix to postfix, so the idea is very simple, what we will do.
So first of all, move the opponent.
So we have operators.
And we have operands.
So operators means plus, multiply, minus and divide.
OK, plus or minus divide and so on.
OK, and operators are basically indigence on which we have to perform the opera operations.
OK, so what will do, move the operators to the closing brackets.
So similarly.
Fort Bliss, this is the closing record.
OK, so remove, multiply, remove, divide from here and put it here similarly, remove place from
here and put glass here.
Now read this from left to right.
So first of all, we have four.
So we will write for then.
Plus is not here because it is here, then we will not read the opening record.
So we will read 13.
So I will read 13.
Then the divide is not there.
We have five.
So I will write five.
Then we have this multiply.
So remove this.
So we have divide.
Sorry.
So I will write divide then.
At this point I have plus so I will write plus.
So this is basically.
The postfix notation.
OK, so this is a postfix notation.
Let us take one more example.
OK, so suppose I have let's say.
Two plus one.
And two, three.
OK, so this is basically infix and we have to convert this into postfix so how we can do this.
So the idea is very simple, but we have to do we have to move the operators.
So for plus it's closing bracket.
Is this so right.
Plus here.
Again, remove it from here.
So for multiply, it's closing record.
Is this OK?
So remove, multiply from here and right, multiply here and then read from left to right.
So first I have this to you.
Do not consider this opening and closing brackets.
OK, so first I have to.
So I will write to then Plus's naughtier then I have one so I will write one.
Then I have Pless so I will write plus then I have three so I will write three.
Then I have multiply so I will write multiply.
OK, so this is the corresponding postfix notation you can see in the above example.
Also saw two one plus three multiply.
OK, so do one blessed three multiply.
OK, so the input is given a postfix expression and we have to evaluate.
So basically if the expression was infix, we can see our answer will be nine.
We can easily calculate.
OK, so in this case, our answer will be six.
So this is an integer division.
So whenever integer upon integer we will get integer only.
So this is basically two.
We will get two and four plus two is six.
OK, so now let's see how to evaluate postfix expression.
So basically there are some rules on how to evaluate for expression and we will simply follow the rules.
OK, if you don't know the rules, you cannot solve this question.
OK, so there are basically defined rules.
To solve the postfix expression.
OK, and you have to remember this rules, OK, if you don't know the rules, you can resolve this question.
OK, so the rules are very simple, so let us consider an example first.
So the first two and one plus three and multiply.
So this is a postfix notation.
So the rules are very, very simple.
OK, so what are the rules?
So obviously, I will have operators.
And I will have opening's.
So operators will be like plus minus multiply and divide.
OK, so for operators to work, I should have two options.
I'll get to should be able to be for example, you can only use plus when I have to options E plus B
minus B, E multiplier baby and a divided baby.
OK, so we need to operands.
To apply the operators.
OK, so the idea is very simple, maintain a stake so you have a stake in the stake is empty.
So you are standing at this point.
So if it is an open end, so if it is to then push, this is open push.
Now I have an operator, so I have operator.
So I have to perform operation.
OK, so we're performing the operation.
What I will do, I will pop one, I will pop two and I will do the operation.
So I will do two plus one.
OK, I am writing it here.
So at this point what will happen?
I will pop the top two element of the stack and I will do the operation.
So I will write two plus one.
OK, so at this point, what I am doing pop the two elements.
So that we can apply the plus operating between them, so pop, two elements apply plus operator, so
after playing the plus operators, so we will get the result three and then put Bush result three inside
the stick Bush result.
So the result is three.
So what we will do, we will push the result.
So three will come inside the stack.
OK.
Now, again, so I have an option, if it is an option, you can basically push, OK, now I have an
operator, so if it is an operator, what we have to do, we have to pop two elements.
So simply follow the step up, two elements.
So two elements are three and three.
So the two elements are three and three.
Then what I have to do, I have to apply the operator.
So in this case, our operators multiply.
So we will apply the operator.
We will get the result and result will be nine and then we have to push the result.
OK, so basically these two elements are public.
I have to push the result.
So I will push the result nine and then I will reach at the end.
OK, so what will be our answer?
So finally, our answer will be the element present at this Dec. 11 percent detail of the strike.
So stack as dot, dot, dot, dot, dot will be our answer.
So our answer is nine.
OK, let's see so we can see.
Our answer is nine.
OK, now let us.
Used the same approach on this for three, four, 13, five.
Divide and class, OK, 48 in five divided plus.
So I have four, 13, five divide plus.
So we know the rules are very simple.
If it is an integer, push inside the stick.
OK, so at this point, what will happen?
So this is an integer, which we have integer, which we have integer.
Bush, we have an op ed, so if it is an operator, obviously we need to eliminate, so we need to eliminate.
So how we will get to elements, we will get the two elements with the help of Steck.
So with the help of Steg, I will Bob Fife and I will pop 13.
OK, so remove five and 13.
So I have to eliminate 13 and five.
And then obviously we have to apply the operator.
So applied the operator after applying the operator.
Our result will be 13 by five, which is two.
OK, so this is our result.
And now what we have to do, we have to push that result inside the stack.
So too will come here.
OK, now, again, move ahead, so I have basically plus so plus that means we need two elements.
OK, and how we will get there to eliminate simply we will take the two elements from the top of the
stack, so remove two and remove four.
So I have four and I have two.
And then what we have to do, we have to apply the operator operators.
So we will apply the operator.
Our result will come out to be six and then we would have to do we have to push the result inside the
stack.
OK, and then I will reach at the end.
So after reaching the end, what will be our answer?
Our answer is basically the top element of the stack, which is six.
OK, so for this case, our output is six and we can see here.
Our output was six.
OK, so basically our goal is working, our logic is 100 percent correct.
OK, now you can assume here.
OK, so you can assume that.
What we can assume, so the input given to us, they input postfix expression given to us is basically
a valid expression.
OK, this is a valid expression that we can assume.
OK, so now let us write the code.
So basically the rules are very simple.
So no one, if it is an open.
If operand, then simply push.
Second guess it is operator.
So if it is operator, then it is very simple, you need two elements to perform the operation and how
you will get to elements simply the top of this track.
OK.
Perform the operation, we will perform plus, minus multiply, divide, so plus minus, multiply and
divide and then you will get the result.
So Bush that is held inside this deck.
And finally, what will happen is finally our answer basically will be the element, there will be only
one element at the end.
OK, so at the end there will be only one element inside the stack and that element will be our answer.
OK, there will be only one element at the end and it will be our answer.
So that is basically the last remaining element of the stack.
And we can get that element with the help of the top.
OK, now let us read the gold.
So if you have understood the solution, if you understood the logic, writing code is very easy.
So first of all, what we need, we need a stack and stack of integers, basically, OK, we are storing
and beta inside the stack.
So the name of the stack is empty.
Now, if we have to do, we are simply iterating.
So let us separate.
So equal zero I listin.
Tokens, Dot says.
And I placeless, so we are trading OK, now what we have to do so.
If the top element is an apprentice, we will push and if it is appropriate, so if it is an operator.
So basically if tokens of a equal equal plus or tokens of a
minus or tokens of a equal equal multiply or tokens of a ecological divide.
So if this is the scenario, then what we have to do, so if it is the operator, we have to push,
we have to pop two elements, OK, so we need two elements here to perform the operation.
We need two elements.
OK, so now let's get both the elements and we will get the elements from the stack, so let's name
it value one, which is a start top.
And astronaut Bob.
Now, let us get our second value, our second element, so we do again our top, an astronaut, Bob
Stegner.
Double standard.
Double standard, Bob.
OK, so we have our board, the elements now, let us perform the operation, so if.
Tokens of equal, equal, plus, then what we have to do, we will add we want and we do OK so as to
not so first find the result and then push.
So I have to do with two plus one.
OK, I am finding the result.
So Bush result inside the deck.
OK, so push the result inside stick.
Now, similarly.
So elusive.
If tokens of A is minus, we have separate operations, so I will do we do minus Reven.
Similarly.
And if I have multiply operation.
I will do over to multiply one, and if I have the divide operation.
So I will do we do divided by one.
OK, and that's all now.
Now, in the Elzbieta, what we have, so we have options here.
Now, we discussed if we have an option, we can basically push inside the stack.
So what I will write is to not push and we can basically push Dawkins off a.
But there's a problem here and what is the problem?
So first of all, this will be Bush.
So what is the problem?
So basically this bag is often details.
OK, so I have created a stack of often teachers and tokens of I is basically a string.
OK, so it is basically a string, for example, tartine, for example, to five, for example, to
OK, so this is basically a string and our stack, our stack is of integers.
So what I have to do, I have to convert the string into integers.
OK, so this is our problem.
I have to convert the string into integers so that I can push integer inside the deck.
OK, so basically we do not have to write code for this.
We have inbuilt function and the name of the function is to say, OK, so what it does, it will take
a string as input.
And it will give me the integer as output.
OK, so if I will give it away basically a string, let's say 45, then it will give me integer 45.
OK, so that is the functionality of it to wavefunction.
OK, so this function is present inside the inside some library of C++.
OK, so this function is already implemented.
We do not have to implement this, but there is a problem with this, a two way function and what is
the problem.
So the problem is basically very simple.
So I'm explaining it here.
So first thing you understand that why we have to convert string into integer, because our input,
the input that is given to us is basically a string and the stack that we have created is basically
often tedious.
So that's why I have to convert a string in 2010.
OK, now the second thing, how to convert into integer.
So I'm telling you, we have a function in the way I will give a string as input and it will give me
the integer value.
Simple, but there's again a problem with a two way function and the problem with it is so in C++ there
is basically two types of string.
OK, so there are two types of strings, so first one is the C strange string C style.
So this is basically the character.
OK.
And the second one is basically the string class.
OK, so this is.
This is basically distinctness.
And it wavefunction takes in Putsy style strength and not this C++ type string.
OK, so what I have to do, so I have to convert this string in to see Strela string.
OK, so basically I am repeating myself in C++ we have two types of string.
So first one is this e-mail and the second one is basically the string class.
OK, so here I will write string as.
And this is the character, Mary, so it wavefunction takes input, see style string, basically correct
type string.
And the input which is given to us is basically the second by posting.
So there should be a way to convert this string and do this character, Eddie, and for converting.
So we have a function called Dot C and a score SDR.
OK, so this is the function which is used to convert this type of string into the correct.
So what I will write, I will write you to away.
I have the input, which is this tape and what I will do, I will write, not see and the score SDR.
OK, so that's how it will work.
OK, so this string is basically this is a token of a token of fire is basically a string.
Now, let us write the code.
So I cannot write like this sort of.
This is basically a string, so for converting string into integer, I have to use it to wavefunction.
But this is not enough, not enough, because it's wavefunction will give us added that this dog that
they did expect a sea style sting.
So what I have to do, I have to use dot see in the square star so that ci a. could steer.
So all these functions are in functions.
OK, you do not have to worry about this, and if your doubt is how I know about these functions is
basically at this point when I first of all, this question, at this point, I get confused how to
solve.
Then I search on the Internet and I came up with the solutions.
OK, so that's how everyone learns.
So finally, when I will come out of this loop.
So what will happen?
So this is Ms.
OK, so when I will come out of this loop, so basically I will have only one element inside the stick,
so only one element inside the stick, and that will be our answer.
So let us return our answer so we're done Steck, dot, dot.
OK, you can see the return type of the function is in Pejar.
That's why I have created this stack of integers.
OK, so finally I can write like this.
They don't stack up.
So I think I have done everything correctly.
Now let us try to run our code.
OK, so there is some problem with the Blackwood's.
OK, so there will be one more Beckert.
Not at a summit, our called.
OK, so our goal is working fine, so what is the time and the space complexity?
OK, so basically the time complexity, we are just getting over the edge over the strings of time.
Complexity is on and we are using we are creating a stack.
So the space complexities on OK, so this is the time and the space complexity of a solution.
OK, so I hope you understood this.
I hope you understood this problem and also the solution.
So basically you can see reverse policy notation.
OK, so this is the another name for postfix rotation policy expression.
OK, so if you have any doubt in this problem, it everyday approach or either with the or you can ask
me.
OK, thank you.