1
00:00:00,740 --> 00:00:01,730
Welcome back.

2
00:00:01,730 --> 00:00:07,400
Let's now go ahead and code the solution, which we discussed in the previous video to solve the reverse

3
00:00:07,400 --> 00:00:08,990
Polish notation question.

4
00:00:08,990 --> 00:00:15,830
Now let's call this function ref pol naught, which is just an abbreviation for reverse Polish notation.

5
00:00:15,830 --> 00:00:19,370
And this function is going to take in the array which is given to us.

6
00:00:19,370 --> 00:00:21,290
And let's call that array tokens.

7
00:00:21,290 --> 00:00:26,570
So inside this array we will either have integers or we will have the valid operators which is plus

8
00:00:26,570 --> 00:00:28,520
minus into and division.

9
00:00:28,520 --> 00:00:31,340
So to start with let's have a stack.

10
00:00:31,340 --> 00:00:33,800
And we're going to implement the stack as an array.

11
00:00:33,800 --> 00:00:35,150
So const stack.

12
00:00:35,150 --> 00:00:36,980
And this is just an empty array.

13
00:00:38,290 --> 00:00:45,310
Now let's just have an object and let's define the valid operators so that we can just call this function

14
00:00:45,310 --> 00:00:45,640
later.

15
00:00:45,640 --> 00:00:45,910
All right.

16
00:00:45,910 --> 00:00:50,560
So when after we identify that it's a plus for example in the tokens array.

17
00:00:50,560 --> 00:00:53,800
So we need to have a function that does the addition right.

18
00:00:53,800 --> 00:00:56,020
So let's just have an object over here.

19
00:00:56,020 --> 00:01:01,480
And the keys in the object is going to be plus minus division and multiplication.

20
00:01:01,480 --> 00:01:07,450
And the value for those keys is going to be the function where we taking the two numbers and do that

21
00:01:07,450 --> 00:01:08,500
particular operation.

22
00:01:08,500 --> 00:01:11,500
So let's call the object valid operators.

23
00:01:17,740 --> 00:01:18,220
All right.

24
00:01:18,220 --> 00:01:19,630
Now this is an object.

25
00:01:19,630 --> 00:01:24,280
And the keys possibilities are plus there we can have plus.

26
00:01:25,530 --> 00:01:28,800
And if we have plus the operation it's a function.

27
00:01:28,800 --> 00:01:29,070
All right.

28
00:01:29,070 --> 00:01:30,450
So we have two numbers.

29
00:01:30,450 --> 00:01:33,000
So let's just call it n1 and n2.

30
00:01:33,030 --> 00:01:34,530
So these are the two numbers.

31
00:01:34,530 --> 00:01:39,540
And then what we will do is we will return n1 plus n2.

32
00:01:41,490 --> 00:01:45,210
Now, the next possibility in terms of a key is minus.

33
00:01:45,240 --> 00:01:49,410
Now, if you are getting minus again we have a function and we have n one.

34
00:01:49,410 --> 00:01:51,330
And n two is the two numbers.

35
00:01:51,330 --> 00:01:55,020
And we will just return n one minus n two.

36
00:01:55,920 --> 00:01:59,370
The next possible operator is multiplication.

37
00:01:59,730 --> 00:02:05,850
If you get that, then again we have a function n1 n2 and we give back.

38
00:02:08,290 --> 00:02:10,450
N1 into N2.

39
00:02:11,310 --> 00:02:13,530
And finally, we could also have division.

40
00:02:13,530 --> 00:02:23,160
And if we have division, then again we have a function n1 n2 and we give back n1 divided by n2.

41
00:02:23,670 --> 00:02:26,760
And then the important thing is that we have to truncate this right.

42
00:02:26,760 --> 00:02:28,380
So that's mentioned in the question.

43
00:02:28,410 --> 00:02:32,340
So for this let's just use math dot trunk over here.

44
00:02:33,540 --> 00:02:35,130
So math dot trunk.

45
00:02:35,130 --> 00:02:38,160
And then we are passing n1 divided by n2 to it.

46
00:02:38,160 --> 00:02:38,790
So that's it.

47
00:02:38,790 --> 00:02:40,080
So this is our object.

48
00:02:40,740 --> 00:02:45,600
Now let's proceed and iterate through the array which is given to us which is tokens.

49
00:02:45,600 --> 00:02:48,390
So we can say for let token.

50
00:02:49,420 --> 00:02:50,620
Of tokens.

51
00:02:52,550 --> 00:02:57,830
So we're taking each element and then we're going to check if it is a operator.

52
00:02:57,830 --> 00:02:58,100
All right.

53
00:02:58,100 --> 00:02:59,780
So there are two possibilities.

54
00:02:59,780 --> 00:03:03,140
It could either be an operator or it can be an integer right.

55
00:03:03,140 --> 00:03:04,610
So if it is an operator.

56
00:03:04,610 --> 00:03:05,600
So let's just check that.

57
00:03:05,600 --> 00:03:06,410
So if.

58
00:03:07,220 --> 00:03:08,720
Valid operator.

59
00:03:09,790 --> 00:03:11,200
At token, right?

60
00:03:11,380 --> 00:03:17,770
So that means if there is a key which has the value token in the valid operator object, which we just

61
00:03:17,770 --> 00:03:18,700
now created over here.

62
00:03:18,700 --> 00:03:25,930
So that means if the token is among plus minus into or division, if that is the case then we have to

63
00:03:25,930 --> 00:03:29,080
identify the two numbers which is which are there in our stack.

64
00:03:29,110 --> 00:03:30,880
The latest two numbers.

65
00:03:30,880 --> 00:03:31,120
Right.

66
00:03:31,120 --> 00:03:32,680
So we have to identify those two.

67
00:03:32,680 --> 00:03:39,070
And remember when we first pop out that's going to be equal to number two as we discussed in the previous

68
00:03:39,070 --> 00:03:39,520
video.

69
00:03:39,520 --> 00:03:41,380
So let's again have two variables.

70
00:03:41,380 --> 00:03:44,530
Let n two be equal to stack.pop.

71
00:03:46,920 --> 00:03:48,510
And then we have n one.

72
00:03:48,510 --> 00:03:51,690
So let n one be equal to stack.pop.

73
00:03:53,820 --> 00:03:56,880
And then we just need to, uh, give the result.

74
00:03:56,880 --> 00:04:03,180
So the result will be the value that we get when we pass that when, when we pass the numbers to that

75
00:04:03,180 --> 00:04:04,680
particular respective function.

76
00:04:04,680 --> 00:04:07,650
So for this let's say again let's have a variable.

77
00:04:07,650 --> 00:04:09,000
So let's say let result.

78
00:04:09,910 --> 00:04:13,960
Is equal to a valid operator at token.

79
00:04:14,660 --> 00:04:16,730
And then we have to pass in the numbers.

80
00:04:17,440 --> 00:04:19,360
N1 comma n2.

81
00:04:20,260 --> 00:04:20,650
All right.

82
00:04:20,650 --> 00:04:22,660
So what what this does is valid.

83
00:04:22,660 --> 00:04:25,810
Operator at token will decide which function to call.

84
00:04:25,810 --> 00:04:28,660
For example if it's plus it will call this function over here.

85
00:04:28,660 --> 00:04:31,540
And then we are passing n1 and n2 to this function.

86
00:04:31,540 --> 00:04:33,850
And we will get back n1 plus n2.

87
00:04:33,850 --> 00:04:35,620
So this is going to be the result.

88
00:04:35,620 --> 00:04:39,280
Now what we need to do is we need to push the result to our stack.

89
00:04:39,280 --> 00:04:41,110
So we can say stack dot push.

90
00:04:43,220 --> 00:04:43,850
Result.

91
00:04:45,150 --> 00:04:45,450
All right.

92
00:04:45,450 --> 00:04:46,080
So that's it.

93
00:04:46,080 --> 00:04:52,380
So then we again that's that's the case where the token in our tokens array is an operator.

94
00:04:52,380 --> 00:04:53,910
So that's the if condition over here.

95
00:04:53,910 --> 00:04:56,310
If that is not the case then we have an else over here.

96
00:04:56,400 --> 00:05:01,260
So if it's an integer then what we do is we are just going to push it to our stack.

97
00:05:01,260 --> 00:05:03,510
So we can we can say stack dot push.

98
00:05:05,970 --> 00:05:06,960
Pass int.

99
00:05:09,660 --> 00:05:10,290
Token.

100
00:05:11,960 --> 00:05:12,500
Again.

101
00:05:12,500 --> 00:05:14,510
Why is it that we're doing parcent over here?

102
00:05:14,510 --> 00:05:15,950
Because in the question.

103
00:05:15,950 --> 00:05:16,160
Right.

104
00:05:16,160 --> 00:05:21,650
So in the question, if, for example, if this is our array and if we have an integer one, so it's

105
00:05:21,650 --> 00:05:24,770
not mentioned as one, but rather it's mentioned like this, right.

106
00:05:24,770 --> 00:05:26,480
So it's a string with value one.

107
00:05:26,480 --> 00:05:28,790
So that's why we have to convert it to an integer.

108
00:05:28,790 --> 00:05:30,440
And then we are pushing it to our stack.

109
00:05:30,440 --> 00:05:32,240
So that's why we have parseint over here.

110
00:05:32,240 --> 00:05:34,280
And then we are passing the token over here.

111
00:05:34,280 --> 00:05:34,580
All right.

112
00:05:34,580 --> 00:05:35,240
So that's it.

113
00:05:35,240 --> 00:05:40,910
Now we just need to keep doing this and loop through the tokens array which is given to us.

114
00:05:40,910 --> 00:05:45,860
And once we are out of this, once we have completed iterating through the array which is given to us,

115
00:05:45,860 --> 00:05:49,490
we just have to give back the last value in the stack.

116
00:05:49,490 --> 00:05:52,040
So we just have to return stack dot pop.

117
00:05:55,370 --> 00:05:56,150
And that's it.

118
00:05:56,150 --> 00:05:56,540
All right.

119
00:05:56,540 --> 00:05:57,650
So this should work.

120
00:05:57,650 --> 00:05:59,480
Now let's go ahead and test our code.

121
00:05:59,480 --> 00:06:00,020
For this.

122
00:06:00,050 --> 00:06:01,490
We will call the function.

123
00:06:01,490 --> 00:06:04,760
And let's pass in an array to it ref all naught.

124
00:06:04,760 --> 00:06:05,990
And let's call it.

125
00:06:05,990 --> 00:06:08,240
And let's pass the tokens array to it.

126
00:06:08,240 --> 00:06:09,680
So let's say we have four.

127
00:06:09,680 --> 00:06:12,110
And let's say after this we have 13.

128
00:06:12,980 --> 00:06:14,840
And then we have five.

129
00:06:16,290 --> 00:06:21,360
And after this, let's say we have division and let's say we have addition.

130
00:06:23,130 --> 00:06:28,110
Now let's run the code and you can see we are getting back six which is correct right.

131
00:06:28,110 --> 00:06:29,640
So let's try to evaluate this.

132
00:06:29,640 --> 00:06:31,380
So let's grab a pen for this.

133
00:06:31,830 --> 00:06:37,470
So the function over here is the the array over here is 413 five division and addition.

134
00:06:37,470 --> 00:06:40,860
So what happens is let's walk through the code and see what's happening.

135
00:06:40,860 --> 00:06:44,610
So let me just make this a little bit smaller so that we can see this.

136
00:06:47,590 --> 00:06:47,890
All right.

137
00:06:47,890 --> 00:06:50,050
So over here we have let me just write this over here.

138
00:06:50,050 --> 00:06:51,610
So we have four.

139
00:06:51,640 --> 00:06:55,930
Then we have 13 five division and addition.

140
00:06:57,910 --> 00:06:59,350
Now we come over here.

141
00:06:59,350 --> 00:07:01,600
Now our stack is going to be empty.

142
00:07:02,140 --> 00:07:04,660
So let's say this is our stack which is just empty.

143
00:07:05,260 --> 00:07:08,440
And we have defined the valid operators over here.

144
00:07:08,440 --> 00:07:10,870
And then we come over here we are iterating through the array.

145
00:07:10,870 --> 00:07:13,030
So first we see that we get four.

146
00:07:13,030 --> 00:07:13,480
All right.

147
00:07:13,480 --> 00:07:15,880
And it's not there in our object.

148
00:07:15,880 --> 00:07:18,580
So we come over here and we are pushing it to our stack.

149
00:07:18,580 --> 00:07:19,720
And we are passing it.

150
00:07:19,720 --> 00:07:21,130
And we are making it an integer.

151
00:07:21,130 --> 00:07:23,140
And we are adding it to our stack over here.

152
00:07:23,140 --> 00:07:28,510
Again we are taking the next value, which is 13, which is not there in the object, the valid operator

153
00:07:28,510 --> 00:07:29,350
object over here.

154
00:07:29,350 --> 00:07:32,890
So we come over here and then we're going to push it to our stack.

155
00:07:32,920 --> 00:07:36,040
We are passing it making it an integer and pushing it to our stack.

156
00:07:36,040 --> 00:07:38,260
And then we take the next value again.

157
00:07:38,260 --> 00:07:40,660
It's not there in the valid operator object.

158
00:07:40,660 --> 00:07:43,420
So we come to the else part and we push it to our stack.

159
00:07:43,420 --> 00:07:44,680
So we get five over here.

160
00:07:44,680 --> 00:07:47,650
Next we see that we are getting division over here.

161
00:07:47,680 --> 00:07:51,970
Now when we check this valid operator at division we see it's there right.

162
00:07:51,970 --> 00:07:53,020
So we see it's there.

163
00:07:53,020 --> 00:07:54,880
So this over here this is truthy.

164
00:07:54,880 --> 00:07:56,200
And we come inside.

165
00:07:56,200 --> 00:07:58,780
So n two is going to be equal to stack dot pop.

166
00:07:58,780 --> 00:08:00,460
So n two is equal to five.

167
00:08:03,320 --> 00:08:04,190
Again, we pop.

168
00:08:04,190 --> 00:08:06,260
So n one is going to be equal to 13.

169
00:08:07,890 --> 00:08:12,360
And then result is equal to valid operator at token which is division.

170
00:08:12,360 --> 00:08:15,300
So we get back this value over here which is this function.

171
00:08:15,300 --> 00:08:19,560
And to the function we are passing n1 and n2 which is 13 and five.

172
00:08:19,560 --> 00:08:23,760
So we are doing 13 divided by five which gives us two point something.

173
00:08:23,760 --> 00:08:25,200
And then we are truncating this right.

174
00:08:25,200 --> 00:08:28,290
So we are removing the decimals and we are getting two over here.

175
00:08:28,290 --> 00:08:28,950
All right.

176
00:08:28,950 --> 00:08:31,170
So the result is going to be equal to two.

177
00:08:31,170 --> 00:08:35,340
And then when we come to this line of code we are going to push this two to our stack.

178
00:08:35,340 --> 00:08:36,570
So this is added over here.

179
00:08:36,900 --> 00:08:38,340
And again we move ahead.

180
00:08:38,340 --> 00:08:44,010
We come over here and we take the next uh item in our tokens array which is addition.

181
00:08:44,010 --> 00:08:48,990
So again when we check this valid operator at addition we see it's truthy because it's there.

182
00:08:48,990 --> 00:08:53,370
So we come inside this and we are again going to identify n1 and n2.

183
00:08:53,370 --> 00:08:53,520
Right.

184
00:08:53,520 --> 00:08:55,470
So let me just clean this up.

185
00:08:55,470 --> 00:08:57,900
So n2 is going to be stack.pop.

186
00:08:57,900 --> 00:09:02,010
So this is n2 and n1 is going to be the next one when we pop.

187
00:09:02,010 --> 00:09:03,210
So we get four over here.

188
00:09:03,210 --> 00:09:06,480
And then we are saying result is equal to valid operator at token.

189
00:09:06,480 --> 00:09:07,950
Token was plus right.

190
00:09:07,950 --> 00:09:11,400
So we are going to get back this function as the value.

191
00:09:11,400 --> 00:09:13,380
And we are passing n1 and n2 to it.

192
00:09:13,380 --> 00:09:17,940
So this will return n1 plus n2 which is four plus two which is equal to six.

193
00:09:17,940 --> 00:09:19,920
So result is going to be equal to six.

194
00:09:19,920 --> 00:09:22,830
And then over here we are just pushing this to our stack.

195
00:09:22,830 --> 00:09:24,360
So we are adding it over here.

196
00:09:24,360 --> 00:09:27,870
And then finally we are going to return whatever we have in the stack.

197
00:09:27,870 --> 00:09:29,610
So Stack.pop will give back six.

198
00:09:29,610 --> 00:09:30,720
And that's the answer.

199
00:09:30,720 --> 00:09:33,930
So this is how the the algorithm that we have written works.

200
00:09:33,930 --> 00:09:36,240
Now what is the space and time complexity of this.

201
00:09:36,240 --> 00:09:37,680
Let's take a quick look at that.

202
00:09:38,190 --> 00:09:43,170
You can see we have to actually traverse the array which is given to us which is the tokens array.

203
00:09:43,170 --> 00:09:43,590
Right.

204
00:09:43,590 --> 00:09:47,580
And if there are n elements in the tokens array we have to do n operation.

205
00:09:47,580 --> 00:09:50,610
So this for loop over here accounts for n operations.

206
00:09:50,610 --> 00:09:55,080
And then inside that we are just checking if something is there in the object.

207
00:09:55,080 --> 00:09:57,060
And if not we are.

208
00:09:57,060 --> 00:10:01,320
And then over here as well as over here we are just pushing or popping from a stack.

209
00:10:01,320 --> 00:10:04,050
So these are all just constant time operations right.

210
00:10:04,050 --> 00:10:08,940
So that's why we can say that the time complexity, which is accounted for by this loop over here,

211
00:10:08,940 --> 00:10:11,070
is going to be of the order of n.

212
00:10:11,070 --> 00:10:13,380
So time complexity is O of n.

213
00:10:13,560 --> 00:10:18,930
Now what about the space complexity we are going to take up space by because we are using this stack

214
00:10:18,930 --> 00:10:19,230
over here.

215
00:10:19,230 --> 00:10:19,590
Right.

216
00:10:19,590 --> 00:10:20,520
We have a stack.

217
00:10:20,520 --> 00:10:22,320
This is going to take up auxiliary space.

218
00:10:22,320 --> 00:10:24,450
And we just want an upper bound.

219
00:10:24,450 --> 00:10:29,010
Again it will not have all the n elements at the same time in the stack, which is true because we are

220
00:10:29,010 --> 00:10:31,890
only inserting numbers and then results from operations.

221
00:10:31,890 --> 00:10:36,660
But again, if we just want an upper bound, this is not going to be greater than n, right?

222
00:10:36,660 --> 00:10:41,430
So we can say that the space complexity of this solution is going to be of the order of n.