Welcome back.
Let's now go ahead and code the solution, which we discussed in the previous video to solve the reverse
Polish notation question.
Now let's call this function ref pol naught, which is just an abbreviation for reverse Polish notation.
And this function is going to take in the array which is given to us.
And let's call that array tokens.
So inside this array we will either have integers or we will have the valid operators which is plus
minus into and division.
So to start with let's have a stack.
And we're going to implement the stack as an array.
So const stack.
And this is just an empty array.
Now let's just have an object and let's define the valid operators so that we can just call this function
later.
All right.
So when after we identify that it's a plus for example in the tokens array.
So we need to have a function that does the addition right.
So let's just have an object over here.
And the keys in the object is going to be plus minus division and multiplication.
And the value for those keys is going to be the function where we taking the two numbers and do that
particular operation.
So let's call the object valid operators.
All right.
Now this is an object.
And the keys possibilities are plus there we can have plus.
And if we have plus the operation it's a function.
All right.
So we have two numbers.
So let's just call it n1 and n2.
So these are the two numbers.
And then what we will do is we will return n1 plus n2.
Now, the next possibility in terms of a key is minus.
Now, if you are getting minus again we have a function and we have n one.
And n two is the two numbers.
And we will just return n one minus n two.
The next possible operator is multiplication.
If you get that, then again we have a function n1 n2 and we give back.
N1 into N2.
And finally, we could also have division.
And if we have division, then again we have a function n1 n2 and we give back n1 divided by n2.
And then the important thing is that we have to truncate this right.
So that's mentioned in the question.
So for this let's just use math dot trunk over here.
So math dot trunk.
And then we are passing n1 divided by n2 to it.
So that's it.
So this is our object.
Now let's proceed and iterate through the array which is given to us which is tokens.
So we can say for let token.
Of tokens.
So we're taking each element and then we're going to check if it is a operator.
All right.
So there are two possibilities.
It could either be an operator or it can be an integer right.
So if it is an operator.
So let's just check that.
So if.
Valid operator.
At token, right?
So that means if there is a key which has the value token in the valid operator object, which we just
now created over here.
So that means if the token is among plus minus into or division, if that is the case then we have to
identify the two numbers which is which are there in our stack.
The latest two numbers.
Right.
So we have to identify those two.
And remember when we first pop out that's going to be equal to number two as we discussed in the previous
video.
So let's again have two variables.
Let n two be equal to stack.pop.
And then we have n one.
So let n one be equal to stack.pop.
And then we just need to, uh, give the result.
So the result will be the value that we get when we pass that when, when we pass the numbers to that
particular respective function.
So for this let's say again let's have a variable.
So let's say let result.
Is equal to a valid operator at token.
And then we have to pass in the numbers.
N1 comma n2.
All right.
So what what this does is valid.
Operator at token will decide which function to call.
For example if it's plus it will call this function over here.
And then we are passing n1 and n2 to this function.
And we will get back n1 plus n2.
So this is going to be the result.
Now what we need to do is we need to push the result to our stack.
So we can say stack dot push.
Result.
All right.
So that's it.
So then we again that's that's the case where the token in our tokens array is an operator.
So that's the if condition over here.
If that is not the case then we have an else over here.
So if it's an integer then what we do is we are just going to push it to our stack.
So we can we can say stack dot push.
Pass int.
Token.
Again.
Why is it that we're doing parcent over here?
Because in the question.
Right.
So in the question, if, for example, if this is our array and if we have an integer one, so it's
not mentioned as one, but rather it's mentioned like this, right.
So it's a string with value one.
So that's why we have to convert it to an integer.
And then we are pushing it to our stack.
So that's why we have parseint over here.
And then we are passing the token over here.
All right.
So that's it.
Now we just need to keep doing this and loop through the tokens array which is given to us.
And once we are out of this, once we have completed iterating through the array which is given to us,
we just have to give back the last value in the stack.
So we just have to return stack dot pop.
And that's it.
All right.
So this should work.
Now let's go ahead and test our code.
For this.
We will call the function.
And let's pass in an array to it ref all naught.
And let's call it.
And let's pass the tokens array to it.
So let's say we have four.
And let's say after this we have 13.
And then we have five.
And after this, let's say we have division and let's say we have addition.
Now let's run the code and you can see we are getting back six which is correct right.
So let's try to evaluate this.
So let's grab a pen for this.
So the function over here is the the array over here is 413 five division and addition.
So what happens is let's walk through the code and see what's happening.
So let me just make this a little bit smaller so that we can see this.
All right.
So over here we have let me just write this over here.
So we have four.
Then we have 13 five division and addition.
Now we come over here.
Now our stack is going to be empty.
So let's say this is our stack which is just empty.
And we have defined the valid operators over here.
And then we come over here we are iterating through the array.
So first we see that we get four.
All right.
And it's not there in our object.
So we come over here and we are pushing it to our stack.
And we are passing it.
And we are making it an integer.
And we are adding it to our stack over here.
Again we are taking the next value, which is 13, which is not there in the object, the valid operator
object over here.
So we come over here and then we're going to push it to our stack.
We are passing it making it an integer and pushing it to our stack.
And then we take the next value again.
It's not there in the valid operator object.
So we come to the else part and we push it to our stack.
So we get five over here.
Next we see that we are getting division over here.
Now when we check this valid operator at division we see it's there right.
So we see it's there.
So this over here this is truthy.
And we come inside.
So n two is going to be equal to stack dot pop.
So n two is equal to five.
Again, we pop.
So n one is going to be equal to 13.
And then result is equal to valid operator at token which is division.
So we get back this value over here which is this function.
And to the function we are passing n1 and n2 which is 13 and five.
So we are doing 13 divided by five which gives us two point something.
And then we are truncating this right.
So we are removing the decimals and we are getting two over here.
All right.
So the result is going to be equal to two.
And then when we come to this line of code we are going to push this two to our stack.
So this is added over here.
And again we move ahead.
We come over here and we take the next uh item in our tokens array which is addition.
So again when we check this valid operator at addition we see it's truthy because it's there.
So we come inside this and we are again going to identify n1 and n2.
Right.
So let me just clean this up.
So n2 is going to be stack.pop.
So this is n2 and n1 is going to be the next one when we pop.
So we get four over here.
And then we are saying result is equal to valid operator at token.
Token was plus right.
So we are going to get back this function as the value.
And we are passing n1 and n2 to it.
So this will return n1 plus n2 which is four plus two which is equal to six.
So result is going to be equal to six.
And then over here we are just pushing this to our stack.
So we are adding it over here.
And then finally we are going to return whatever we have in the stack.
So Stack.pop will give back six.
And that's the answer.
So this is how the the algorithm that we have written works.
Now what is the space and time complexity of this.
Let's take a quick look at that.
You can see we have to actually traverse the array which is given to us which is the tokens array.
Right.
And if there are n elements in the tokens array we have to do n operation.
So this for loop over here accounts for n operations.
And then inside that we are just checking if something is there in the object.
And if not we are.
And then over here as well as over here we are just pushing or popping from a stack.
So these are all just constant time operations right.
So that's why we can say that the time complexity, which is accounted for by this loop over here,
is going to be of the order of n.
So time complexity is O of n.
Now what about the space complexity we are going to take up space by because we are using this stack
over here.
Right.
We have a stack.
This is going to take up auxiliary space.
And we just want an upper bound.
Again it will not have all the n elements at the same time in the stack, which is true because we are
only inserting numbers and then results from operations.
But again, if we just want an upper bound, this is not going to be greater than n, right?
So we can say that the space complexity of this solution is going to be of the order of n.