Welcome back.
Let's try to understand how we can solve this question.
Let's take an example.
So we have five six for division addition one and subtraction.
Now we can solve this question using a stack.
Because the interesting thing is that we always need the latest two numbers when we are encountering
an operator.
Right.
So to get this done, to get this solved we can use a stack.
So let's try to see how we can use this.
So initially the stack is empty.
And I'm just implementing the stack over here as an array.
And we are going to traverse the given array which is this array over here.
Let's just call it tokens.
So we're going to traverse the tokens array from left to right.
So whenever we are going to encounter an integer for example over here we have five.
We will just push it to our stack.
So we push five.
Then we get six.
So we push six.
Then we get four.
So we push four also into our stack.
Now we are going to encounter an operator right.
So which is division.
So when we are encountering an operator what we will do is we will have to get the two previous numbers.
So let's have two variables number one and number two.
And then we will just do stack dot pop right.
So we're going to pop out of the stack or remove from the end.
So first we are going to get this four over here.
But again remember the way we are going to operate this is it should be six divided by four.
So whatever we are going to get first when we are popping this will be number two.
So we are going to pop and we get number two and we assign it to number two.
So four is number two.
And then we are going to again pop from the stack.
And we're going to assign that to number one.
So number one is equal to six.
And number two is equal to four.
Now we will just do the operation which is division.
So we go ahead and do six divided by four.
That's equal to 1.5.
And then because in the question it's mentioned that in the case of division we have to truncate towards
zero.
So 1.5 becomes one.
All right.
Now, once we get this one over here again, it's an integer.
So we have to push it to our stack.
So we push this one to our stack.
All right.
So we get one over here.
And then we are going to continue traversing the I the array over here.
So we move ahead.
And after this we can see that this is how our stack looks like at this moment.
So we move ahead and over here we get plus.
All right.
So we again get plus.
So that's an operator.
So we have to identify the previous two numbers.
So we are just going to pop from the stack.
And what are we going to get first is going to be number two.
So number two is one.
And then we pop again.
And that's going to be equal to number one.
So we got five and one.
And then we'll just do the operation.
So five plus one is equal to six.
And this is an integer.
And we have to push this back to our stack.
So we get six again in our stack.
And then we move ahead.
And you can see the stack looks like this.
At the moment we move ahead and we get one over here it's an integer.
So we push it to our stack.
Again we proceed and we get minus which is an operator.
Therefore again we have to identify number one.
And number two.
For this we're going to pop from the stack.
Whatever we are getting first is going to be equal to number two.
So number two is equal to one.
And number one is going to be equal to six.
Again we pop from the stack to get six.
Now we're going to do the operation.
So six minus one that's equal to five.
And again this is an integer.
So we push it back to our stack.
So we get five in our stack.
And then we have completed going through the array.
Right.
So after iterating through the array whatever is the integer that is there in the stack at the end.
Right.
The last element in the stack, that's going to be our answer.
And we can just return this five over here.
So we will just return five.
And that is how we will solve this question.
Now let's take a quick look at the space and time complexity of this solution.
Now you can see that we have to iterate through the array right.
So we have to move traverse the array which is given to us.
So let's say the array has n elements.
In that case we can say the time complexity is o of n again in each of these instances.
So again first let me just write it down over here.
So we are traversing the array.
So that's why the time complexity is O of n.
And also notice that in each of these instances when we are traversing the array we are just checking
if something is there in somewhere, like if it's an operator or if it's an integer.
So we will do that check.
And then if it's an integer, we will push to the stack.
If it's an operator, then we are popping from the stack and doing some operations.
So you can see that all of that is just constant time operations.
Right.
So that's why the time complexity is just O of N.
And what about the space complexity?
Again Big-O analysis gives us an upper bound.
And we know that we are consuming extra space because we have this stack over here.
Now, even though the stack will not have all the n elements at a time.
But still, we can say that it's not going to be more than n, right?
So again, it's not constant space because it will depend, right?
For example, if it's something like this 567813 and then it goes on for a long time, and then the
first operator comes.
So you can say it's not constant space, right.
So it will have all these elements at a time in the stack.
So we can say that the upper bound of the stack of or the space that we are consuming over here is equal
to n.
So the space complexity of this solution is of the order of n.