1
00:00:00,000 --> 00:00:07,833
[No Audio]

2
00:00:07,834 --> 00:00:10,266
Hello and welcome back again. Finally the

3
00:00:10,267 --> 00:00:12,300
wait is over, and in this tutorial we will be

4
00:00:12,301 --> 00:00:14,266
implementing the conversion to postfix.

5
00:00:14,600 --> 00:00:16,566
I am starting with the same script, that we wrote

6
00:00:16,567 --> 00:00:18,733
in the last tutorial. Before starting to

7
00:00:18,734 --> 00:00:20,700
code, it will be useful to have a look at the

8
00:00:20,701 --> 00:00:22,566
rules for conversion to postfix.

9
00:00:22,567 --> 00:00:24,433
[No Audio]

10
00:00:24,434 --> 00:00:27,600
The first rule is related to the priorities. The second

11
00:00:27,601 --> 00:00:29,666
rule is that, if scanned operator is less than

12
00:00:29,667 --> 00:00:31,433
or equal to than the top of the second

13
00:00:31,434 --> 00:00:33,733
priority, then pop operators until we have

14
00:00:33,734 --> 00:00:37,333
low priority, add the popped elements to the postfix.

15
00:00:38,000 --> 00:00:39,766
Next, if we have the opening

16
00:00:39,767 --> 00:00:42,466
parenthesis, then we will just push it into

17
00:00:42,467 --> 00:00:44,100
the stack and if we have a closing

18
00:00:44,101 --> 00:00:46,400
parenthesis, then we will pop elements from

19
00:00:46,401 --> 00:00:48,700
the stack until we reach the opening parenthesis.

20
00:00:49,033 --> 00:00:50,733
And all the popped elements will be

21
00:00:50,734 --> 00:00:53,733
added to the postfix. Finally if we have

22
00:00:53,766 --> 00:00:57,200
operand, we will just add it to the postfix expression.

23
00:00:58,333 --> 00:01:00,233
If we look at the rules from 2 to 5,

24
00:01:00,366 --> 00:01:02,500
there will be checks for each symbol

25
00:01:02,501 --> 00:01:06,433
that is being processed. At any point, at any

26
00:01:06,434 --> 00:01:08,933
time one of these rules will be applicable.

27
00:01:09,133 --> 00:01:11,133
This means that we can use a match statement

28
00:01:11,134 --> 00:01:13,566
for implementing this. Let us define a

29
00:01:13,567 --> 00:01:15,466
function for implementing the conversion to

30
00:01:15,467 --> 00:01:21,033
postfix, I will use the name of infix_to_postfix for this function.

31
00:01:21,666 --> 00:01:23,100
The input to this function will be

32
00:01:23,101 --> 00:01:24,991
a vector of strings, containing the symbols.

33
00:01:24,992 --> 00:01:27,900
[No Audio]

34
00:01:27,901 --> 00:01:30,000
The output of this function will be a vector

35
00:01:30,001 --> 00:01:32,821
of strings, containing the symbols in postfix notation.

36
00:01:32,822 --> 00:01:37,533
[No Audio]

37
00:01:37,534 --> 00:01:39,466
Inside the function, I will first

38
00:01:39,800 --> 00:01:41,900
declare a variable for storing the size of

39
00:01:41,901 --> 00:01:43,900
the input vector of strings, and we'll name it

40
00:01:43,901 --> 00:01:45,861
as size_expr.

41
00:01:45,862 --> 00:01:49,966
[No Audio]

42
00:01:49,967 --> 00:01:52,366
We need the size information to make an appropriate

43
00:01:52,367 --> 00:01:54,666
size stack, which will be used in our

44
00:01:54,667 --> 00:01:56,766
processing of conversion to postfix.

45
00:01:57,400 --> 00:02:01,366
Next, I will make the stack using the new_stack function.

46
00:02:01,367 --> 00:02:05,166
[No Audio]

47
00:02:05,167 --> 00:02:06,666
To store the final postfix

48
00:02:06,667 --> 00:02:09,681
expression, I will declare a vector of strings called postfix.

49
00:02:09,682 --> 00:02:14,300
[No Audio]

50
00:02:14,301 --> 00:02:15,200
Okay we are done with the

51
00:02:15,201 --> 00:02:18,366
variables. Now, next, I am going to iterate

52
00:02:18,367 --> 00:02:20,733
through all the symbols in the input using a for loop.

53
00:02:20,738 --> 00:02:28,200
[No Audio]

54
00:02:28,201 --> 00:02:30,300
Let us get rid of the red lines by returning

55
00:02:30,301 --> 00:02:34,233
postfix outside the for loop, as it is a bit distracting.

56
00:02:34,234 --> 00:02:38,133
[No Audio]

57
00:02:38,134 --> 00:02:39,900
The red line kinds of creates

58
00:02:39,901 --> 00:02:42,566
some distraction, and it is always a good idea

59
00:02:42,567 --> 00:02:44,833
to get rid of them as soon as possible. You

60
00:02:44,834 --> 00:02:47,066
may note, that the type of the variable i is

61
00:02:47,067 --> 00:02:49,433
that of a string and not a string reference,

62
00:02:49,434 --> 00:02:52,100
which means that the variable I assumed

63
00:02:52,101 --> 00:02:53,733
the ownership of the values.

64
00:02:54,400 --> 00:02:57,166
Next, we will do a match on the current symbol, which

65
00:02:57,167 --> 00:02:58,786
is given by the variable i.

66
00:02:58,787 --> 00:03:04,900
[No Audio]

67
00:03:04,901 --> 00:03:07,433
We will put some conditions to check, if rule 2

68
00:03:07,434 --> 00:03:09,733
can be applied or not. Let us see the

69
00:03:09,734 --> 00:03:12,166
rule 2 again. The starting lines of this

70
00:03:12,167 --> 00:03:15,566
rule says that, if operator is less than or

71
00:03:15,567 --> 00:03:17,833
equal to in priority, let us stop reading

72
00:03:17,834 --> 00:03:20,133
here the rule. This means that, this rule is

73
00:03:20,134 --> 00:03:22,733
applicable in case of operator. So let us

74
00:03:22,734 --> 00:03:25,133
have an arm for checking if the

75
00:03:25,134 --> 00:03:26,766
symbol is an operator or not.

76
00:03:26,771 --> 00:03:30,766
[No Audio]

77
00:03:30,767 --> 00:03:33,466
You might note, that the compiler result is complaining about

78
00:03:33,467 --> 00:03:35,933
the types, anything inside the double quotes

79
00:03:35,934 --> 00:03:38,966
is treated as a string reference type and not

80
00:03:39,000 --> 00:03:41,433
a string type. So let us convert the variable

81
00:03:41,434 --> 00:03:44,100
i to that of a string slice type, which can

82
00:03:44,101 --> 00:03:46,666
be done using the as_str function.

83
00:03:47,700 --> 00:03:49,966
Also note that the as_str

84
00:03:49,967 --> 00:03:53,400
does not take ownership as it uses a reference.

85
00:03:54,166 --> 00:03:56,500
We will not write the complete logic inside

86
00:03:56,501 --> 00:03:58,933
this arm right now, we will first complete

87
00:03:58,934 --> 00:04:00,833
the different arms that we may expect

88
00:04:00,834 --> 00:04:02,766
corresponding to different rules, and then we

89
00:04:02,767 --> 00:04:04,500
will add code to each of these ones.

90
00:04:05,433 --> 00:04:08,333
This will help us having a holistic view first.

91
00:04:08,666 --> 00:04:10,766
Let us now add another arm corresponding to

92
00:04:10,767 --> 00:04:13,166
rule 3,4 and 5. The rule 3 and

93
00:04:13,167 --> 00:04:14,966
4 checks for the opening and closing

94
00:04:14,967 --> 00:04:17,766
parenthesis respectively. So I will add an

95
00:04:17,767 --> 00:04:19,833
arm corresponding, to rule 3 first, and

96
00:04:19,834 --> 00:04:20,800
then for rule 4.

97
00:04:20,801 --> 00:04:27,400
[No Audio]

98
00:04:27,401 --> 00:04:29,566
Finally if none of the arms are valid, then

99
00:04:29,567 --> 00:04:31,966
we will have a default default arm which will

100
00:04:31,967 --> 00:04:34,900
correspond to rule 5, and which will mean

101
00:04:34,901 --> 00:04:37,300
that the symbol corresponds to an operand.

102
00:04:37,301 --> 00:04:42,200
[No Audio]

103
00:04:42,201 --> 00:04:44,266
Okay, now the skeletal of our code is more or

104
00:04:44,267 --> 00:04:46,133
less complete. Let us add code to the

105
00:04:46,134 --> 00:04:48,233
individual blocks now one by one.

106
00:04:48,566 --> 00:04:50,633
We will start with the first one which corresponds

107
00:04:50,634 --> 00:04:53,800
to rule 2. To apply rule 2, we will need to

108
00:04:53,801 --> 00:04:55,733
first determine the priority of the operands.

109
00:04:56,000 --> 00:04:57,566
I will define another function

110
00:04:57,567 --> 00:04:59,700
for determining the priority of an operand.

111
00:05:00,366 --> 00:05:03,033
I will name this function as priority, the

112
00:05:03,034 --> 00:05:04,800
input to this function will be a string

113
00:05:04,801 --> 00:05:07,333
reference containing the operator, and the

114
00:05:07,334 --> 00:05:09,400
output will be an unsigned number indicating

115
00:05:09,401 --> 00:05:11,689
the priority corresponding to the input operator.

116
00:05:11,690 --> 00:05:14,700
[No Audio]

117
00:05:14,701 --> 00:05:16,133
Inside the function, we will check

118
00:05:16,134 --> 00:05:18,266
the operator and then assign appropriate

119
00:05:18,267 --> 00:05:20,966
priorities accordingly. I will use the if

120
00:05:20,967 --> 00:05:23,833
else, if structure here to code this part. Of

121
00:05:23,834 --> 00:05:26,100
course, we can also use the match statement

122
00:05:26,101 --> 00:05:29,900
in this case also. First, we will check for

123
00:05:29,901 --> 00:05:32,333
the operator being addition or subtraction,

124
00:05:32,700 --> 00:05:34,962
and we'll set its priority to the minimum value.

125
00:05:34,963 --> 00:05:39,133
[No Audio]

126
00:05:39,134 --> 00:05:40,966
Next, we will set the priorities for

127
00:05:40,967 --> 00:05:43,322
the multiplication and division.

128
00:05:43,323 --> 00:05:47,600
[No Audio]

129
00:05:47,601 --> 00:05:50,284
Finally we will set the priority for the exponent.

130
00:05:50,285 --> 00:05:52,666
[No Audio]

131
00:05:52,667 --> 00:05:55,733
Finally, I will include an else part, where I

132
00:05:55,734 --> 00:05:58,400
will set the priority to that of 0. We need

133
00:05:58,401 --> 00:06:00,900
it because, if you recall the example, there

134
00:06:00,901 --> 00:06:03,400
was a case when we were matching the top of the

135
00:06:03,401 --> 00:06:05,600
stack with that of the opening parenthesis.

136
00:06:05,900 --> 00:06:07,500
And in that case, we mentioned that the

137
00:06:07,501 --> 00:06:09,533
opening parenthesis are considered to have

138
00:06:09,534 --> 00:06:11,500
least priority, compared to any of the

139
00:06:11,501 --> 00:06:14,866
operators. So, to take all that, we will

140
00:06:14,867 --> 00:06:17,633
use this else part, which will corresponds to

141
00:06:17,666 --> 00:06:21,800
an opening parenthesis. Okay, now let us come

142
00:06:21,801 --> 00:06:23,700
back again to the first arm.

143
00:06:23,701 --> 00:06:25,866
[No Audio]

144
00:06:25,867 --> 00:06:28,666
I will first check if the priority of the scanned operator is

145
00:06:28,667 --> 00:06:30,933
greater than the top of the stack, then we

146
00:06:30,934 --> 00:06:33,200
will just push the operator onto the stack.

147
00:06:33,201 --> 00:06:35,466
The priority function will be used to return

148
00:06:35,467 --> 00:06:37,833
the priority in this case, moreover the top

149
00:06:37,834 --> 00:06:39,966
of the stack is given by the last function.

150
00:06:40,666 --> 00:06:42,600
If this condition is true, then we will use

151
00:06:42,601 --> 00:06:44,900
the push function to add the element to the stack.

152
00:06:44,901 --> 00:06:48,500
[No Audio]

153
00:06:48,501 --> 00:06:50,033
Please note that, the last function

154
00:06:50,034 --> 00:06:51,900
when called on the stack, will return a

155
00:06:51,901 --> 00:06:53,700
reference, and therefore the compiler is not

156
00:06:53,701 --> 00:06:55,600
complaining with regards to the input to the

157
00:06:55,601 --> 00:06:58,200
priority function, which accepts a string

158
00:06:58,201 --> 00:07:00,933
reference. When this condition is not true,

159
00:07:00,934 --> 00:07:02,800
which will mean that the top of the stack is

160
00:07:02,801 --> 00:07:05,700
lesser than or equal to in priority, then the

161
00:07:05,701 --> 00:07:08,266
scanned symbol. So in this case, we will pop

162
00:07:08,267 --> 00:07:10,200
elements from the stack until the top of the

163
00:07:10,201 --> 00:07:12,833
stack becomes lesser in priority than the

164
00:07:12,834 --> 00:07:15,600
scanned symbol or the current operator.

165
00:07:15,933 --> 00:07:18,866
To implement this, I will use a while loop,

166
00:07:18,867 --> 00:07:20,866
which will iterate until the priority of the

167
00:07:20,867 --> 00:07:23,700
scanned symbol become lesser to or equal to in

168
00:07:23,701 --> 00:07:25,515
priority than the top of the stack.

169
00:07:25,516 --> 00:07:31,666
[No Audio]

170
00:07:31,667 --> 00:07:33,700
Inside the loop, we will pop the elements from

171
00:07:33,701 --> 00:07:35,533
the stack, and we'll add it to the postfix

172
00:07:35,566 --> 00:07:38,566
expression. These two operations are done

173
00:07:38,567 --> 00:07:40,133
using a single statement.

174
00:07:40,134 --> 00:07:46,800
[No Audio]

175
00:07:46,801 --> 00:07:48,533
Now sometimes it may happen that, while

176
00:07:48,534 --> 00:07:50,400
popping the elements from the stack, we may

177
00:07:50,401 --> 00:07:52,366
reach to the end of the stack, and checking

178
00:07:52,367 --> 00:07:55,033
more elements may therefore leads to an error.

179
00:07:55,400 --> 00:07:57,166
To avoid that, we will write one

180
00:07:57,200 --> 00:07:59,500
additional check before executing the

181
00:07:59,501 --> 00:08:02,066
next iteration of the loop. This will check if

182
00:08:02,067 --> 00:08:04,662
there exists the top element or not.

183
00:08:04,663 --> 00:08:09,466
[No Audio]

184
00:08:09,467 --> 00:08:12,549
If this becomes true, so we will break out from the while loop.

185
00:08:12,550 --> 00:08:17,133
[No Audio]

186
00:08:17,134 --> 00:08:18,500
In this case, the meaning will be

187
00:08:18,501 --> 00:08:20,100
that all the elements in the stack are

188
00:08:20,101 --> 00:08:22,100
greater than or equal to priority than the

189
00:08:22,101 --> 00:08:23,166
current operator.

190
00:08:24,692 --> 00:08:25,800
When the loop ends, we are

191
00:08:25,801 --> 00:08:28,533
sure that the current element

192
00:08:28,534 --> 00:08:30,300
has now greater priority, so it is

193
00:08:30,301 --> 00:08:32,900
safe to push it to the stack.

194
00:08:32,901 --> 00:08:34,033
So let us push it.

195
00:08:35,539 --> 00:08:37,133
Okay, we are almost done with

196
00:08:37,134 --> 00:08:40,166
this arm. But wait, what will happen to the

197
00:08:40,203 --> 00:08:42,504
code when we encounter the first operator?

198
00:08:42,633 --> 00:08:44,833
In this case our stack will be empty. I

199
00:08:44,834 --> 00:08:46,533
will give you 10 seconds to think, and then I

200
00:08:46,534 --> 00:08:47,633
will tell you the answer.

201
00:08:47,634 --> 00:08:58,666
[No Audio]

202
00:08:58,667 --> 00:09:00,433
I believe you would have guessed the answer.

203
00:09:00,434 --> 00:09:02,400
In this case, the if statement will give an

204
00:09:02,401 --> 00:09:05,100
error, because the function stack.last

205
00:09:05,101 --> 00:09:08,333
will return a None value, and we cannot unwrap

206
00:09:08,366 --> 00:09:11,133
an null value. Since this is the first operator

207
00:09:11,134 --> 00:09:13,933
and the stack is empty, we may just add it to

208
00:09:13,934 --> 00:09:16,633
the stack, because the top of the stack is empty.

209
00:09:16,634 --> 00:09:18,633
This means that, we will always add an

210
00:09:18,634 --> 00:09:20,666
operator to the stack if the stack is empty.

211
00:09:20,933 --> 00:09:23,166
To avoid this error, I will include a simple

212
00:09:23,167 --> 00:09:25,300
if statement, which will check the size, and if

213
00:09:25,301 --> 00:09:27,066
the size is 0, then we will push the

214
00:09:27,067 --> 00:09:28,400
operator onto the stack.

215
00:09:28,401 --> 00:09:31,500
[No Audio]

216
00:09:31,501 --> 00:09:34,183
All the remaining code will go to the else part.

217
00:09:34,184 --> 00:09:37,766
[No Audio]

218
00:09:37,767 --> 00:09:41,000
Now this arm is complete, for the next arm, the code is very

219
00:09:41,001 --> 00:09:42,866
simple. When we encountered the opening

220
00:09:42,867 --> 00:09:45,433
parenthesis so the rule 3 says,

221
00:09:45,533 --> 00:09:47,733
that we just need to push it onto the stack.

222
00:09:48,133 --> 00:09:49,821
So let me add a suitable statement.

223
00:09:49,822 --> 00:09:55,666
[No Audio]

224
00:09:55,667 --> 00:09:57,900
Since there is only a single statement inside

225
00:09:57,901 --> 00:10:00,233
this arm, so we do not require the curly brackets.

226
00:10:00,666 --> 00:10:02,566
However for the correct syntax,

227
00:10:02,567 --> 00:10:05,166
we are required to write a comma at the end

228
00:10:05,167 --> 00:10:08,133
of the statement. The next arm corresponds to

229
00:10:08,134 --> 00:10:10,366
the closing parenthesis. In this case, we

230
00:10:10,367 --> 00:10:13,133
will pop up elements until we encountered the

231
00:10:13,134 --> 00:10:15,766
opening parenthesis, all the popped elements will

232
00:10:15,767 --> 00:10:18,633
be added to the postfix expression. I will do

233
00:10:18,634 --> 00:10:21,366
this using a while loop. The while

234
00:10:21,367 --> 00:10:23,966
loop will iterate as long as we do

235
00:10:23,967 --> 00:10:25,994
not encounter the opening parenthesis.

236
00:10:25,995 --> 00:10:32,766
[No Audio]

237
00:10:32,767 --> 00:10:35,730
Inside the loop, I will add the popped elements to the postfix.

238
00:10:35,731 --> 00:10:41,233
[No Audio]

239
00:10:41,234 --> 00:10:43,833
Finally, we will also remove the opening

240
00:10:43,834 --> 00:10:45,901
parenthesis by popping it from the stack.

241
00:10:45,902 --> 00:10:50,466
[No Audio]

242
00:10:50,467 --> 00:10:53,000
This will remove the opening parenthesis from

243
00:10:53,001 --> 00:10:57,000
the stack. Let us now code the default arm.

244
00:10:57,001 --> 00:10:59,366
When none of the arms above is true, then the

245
00:10:59,367 --> 00:11:01,433
default arm will be executed, which is an

246
00:11:01,434 --> 00:11:03,233
indication that the current symbol is an

247
00:11:03,234 --> 00:11:05,866
operand. This means that we are now in rule 5,

248
00:11:05,867 --> 00:11:08,133
and rule 5 says that, we just need to

249
00:11:08,134 --> 00:11:09,800
add the operand to the postfix.

250
00:11:09,801 --> 00:11:11,138
So let us use it.

251
00:11:11,139 --> 00:11:17,100
[No Audio]

252
00:11:17,101 --> 00:11:19,333
Again, as there as a single statement, so we

253
00:11:19,334 --> 00:11:21,666
will remove the brackets and we'll add a comma.

254
00:11:22,533 --> 00:11:24,500
As pointed out in the example, when all

255
00:11:24,501 --> 00:11:26,133
the symbols are scanned, and if there is

256
00:11:26,134 --> 00:11:28,500
something left in the stack, so we will

257
00:11:28,501 --> 00:11:30,933
just pop it until the stack becomes empty,

258
00:11:30,934 --> 00:11:33,633
and we'll add all the elements to the postfix.

259
00:11:33,900 --> 00:11:35,600
We will use a while loop again, which will

260
00:11:35,601 --> 00:11:38,300
iterate until the size of the stack becomes empty.

261
00:11:38,301 --> 00:11:44,633
[No Audio]

262
00:11:44,634 --> 00:11:46,800
Inside the body of the while loop, we will pop

263
00:11:46,801 --> 00:11:48,966
elements from the stack, and we'll add them to

264
00:11:48,967 --> 00:11:50,286
the postfix.

265
00:11:50,287 --> 00:11:53,063
[No Audio]

266
00:11:53,064 --> 00:11:55,400
Okay done, finally, I will print

267
00:11:55,401 --> 00:11:57,198
the resulting expression.

268
00:11:57,199 --> 00:12:01,466
[No Audio]

269
00:12:01,467 --> 00:12:02,700
Now let us move to

270
00:12:02,701 --> 00:12:04,766
the main function, and call this function, and

271
00:12:04,767 --> 00:12:06,913
we'll store the result in postfix variable.

272
00:12:06,914 --> 00:12:12,133
[No Audio]

273
00:12:12,134 --> 00:12:13,833
Let us cargo run this to see the final

274
00:12:13,834 --> 00:12:15,007
postfix expression.

275
00:12:15,008 --> 00:12:21,200
[No Audio]

276
00:12:21,201 --> 00:12:22,866
We have the original expression and the

277
00:12:22,867 --> 00:12:25,400
resultant postfix expression, that is great.

278
00:12:25,700 --> 00:12:27,833
This brings us to the end of this tutorial, we

279
00:12:27,834 --> 00:12:30,233
have implemented how to convert the infix or

280
00:12:30,234 --> 00:12:32,266
original expression to the postfix

281
00:12:32,267 --> 00:12:34,833
expression. While doing so, we have practiced

282
00:12:34,834 --> 00:12:37,300
majority of the concepts that we have learned so far.

283
00:12:37,466 --> 00:12:39,133
Please note that this implementation,

284
00:12:39,134 --> 00:12:41,100
may not be the most optimal one, but the

285
00:12:41,101 --> 00:12:44,200
objective here is not to have an optimal

286
00:12:44,201 --> 00:12:46,000
implementation, but rather practice the

287
00:12:46,001 --> 00:12:49,100
concepts that we have learned so far. Once we

288
00:12:49,101 --> 00:12:50,833
have sufficient skills and programming, we

289
00:12:50,834 --> 00:12:52,600
can always review our code and make the

290
00:12:52,601 --> 00:12:55,266
optimization in code. In the next tutorial, we

291
00:12:55,267 --> 00:12:57,333
will be implementing the last part, and that

292
00:12:57,334 --> 00:12:59,400
will be the computation of the final result

293
00:12:59,401 --> 00:13:01,800
from the postfix expression. Do come back

294
00:13:01,801 --> 00:13:04,200
again for covering that, and until then happy

295
00:13:04,201 --> 00:13:05,433
Rust programming.

296
00:13:05,434 --> 00:13:11,266
[No Audio]