1
00:00:00,000 --> 00:00:08,800
[No Audio]

2
00:00:08,801 --> 00:00:10,900
Welcome back again. I know you have been

3
00:00:10,901 --> 00:00:12,500
waiting for some time now to start

4
00:00:12,501 --> 00:00:14,900
implementing the Expression Evaluation using stack.

5
00:00:15,100 --> 00:00:17,000
So, let's dive into it straightaway.

6
00:00:18,400 --> 00:00:20,800
I am starting with the same code, that we

7
00:00:20,801 --> 00:00:22,800
used and saw, where we were implementing

8
00:00:22,801 --> 00:00:25,200
the stacks with the slight change, which I

9
00:00:25,201 --> 00:00:27,800
will explain in a second. And this

10
00:00:27,801 --> 00:00:30,033
implementation, we assume that the expression

11
00:00:30,034 --> 00:00:32,133
we will be given is in the form of a string.

12
00:00:32,299 --> 00:00:34,600
So, this means there is the individual symbol

13
00:00:34,601 --> 00:00:37,333
expressions that is operands and operators

14
00:00:37,334 --> 00:00:39,733
will be in string format. So, therefore, to

15
00:00:39,734 --> 00:00:41,833
save some time, I have already changed all

16
00:00:41,834 --> 00:00:43,700
the definitions of all the functions of the

17
00:00:43,701 --> 00:00:46,200
stack based on strings. The rest of the code

18
00:00:46,201 --> 00:00:48,300
is more or less the same as that of the code

19
00:00:48,301 --> 00:00:50,333
covered in the first lecture when we were

20
00:00:50,334 --> 00:00:52,800
implementing the stack. Let us now start with

21
00:00:52,801 --> 00:00:54,366
some code in the main function.

22
00:00:55,733 --> 00:00:59,933
I will declare a variable called input_expr

23
00:00:59,934 --> 00:01:01,733
or expr, which contains

24
00:01:01,734 --> 00:01:04,233
the expression that we used in the examples.

25
00:01:04,234 --> 00:01:07,400
[No Audio]

26
00:01:07,401 --> 00:01:09,333
I will print this expression also

27
00:01:09,334 --> 00:01:13,500
[No Audio]

28
00:01:13,501 --> 00:01:16,200
the individual symbols in this string, and

29
00:01:16,201 --> 00:01:18,600
by symbols, I mean operands to be specific, may

30
00:01:18,601 --> 00:01:21,200
contain any number of characters. We cannot

31
00:01:21,201 --> 00:01:23,200
perform operations on the characters in this

32
00:01:23,201 --> 00:01:25,200
case, because the number may occupy more

33
00:01:25,201 --> 00:01:27,500
than one character. For instance, if we have

34
00:01:27,501 --> 00:01:29,300
a number consisting of three digits in the

35
00:01:29,301 --> 00:01:31,400
expression, then it will consume three

36
00:01:31,401 --> 00:01:33,600
characters, and if it is a number such as

37
00:01:33,601 --> 00:01:37,633
1043, then it will consume four characters and so on.

38
00:01:37,634 --> 00:01:39,033
We therefore needs to have a

39
00:01:39,034 --> 00:01:40,700
function, which will return to us the

40
00:01:40,701 --> 00:01:43,100
individual symbols inside the expressions.

41
00:01:44,000 --> 00:01:46,200
I will declare a function for this purpose

42
00:01:46,201 --> 00:01:48,700
called individual symbols.

43
00:01:48,701 --> 00:01:52,100
[No Audio]

44
00:01:52,101 --> 00:01:54,400
This function will convert the given expression into the

45
00:01:54,401 --> 00:01:56,500
individual symbols, and will return the

46
00:01:56,501 --> 00:02:00,100
individual symbols as elements of a string vector.

47
00:02:00,101 --> 00:02:02,033
The input to this function will be a

48
00:02:02,034 --> 00:02:05,266
string, and the output will be a vector of strings.

49
00:02:05,267 --> 00:02:12,966
[No Audio]

50
00:02:12,967 --> 00:02:14,933
Inside the function, I will first declare a

51
00:02:14,934 --> 00:02:16,933
mutable variable which will be used for

52
00:02:16,934 --> 00:02:18,900
storing the final result in the form of

53
00:02:18,901 --> 00:02:23,100
individual symbols. I will call it tokenized_input.

54
00:02:23,533 --> 00:02:24,800
Since the final symbols

55
00:02:24,801 --> 00:02:26,700
will be contained in a vector of strings, so

56
00:02:26,701 --> 00:02:29,400
therefore, I will mention its types to be

57
00:02:29,401 --> 00:02:32,600
that of string back, and we'll initialize it

58
00:02:32,601 --> 00:02:35,433
as an empty string. Next I'm going to

59
00:02:35,434 --> 00:02:37,200
iterate through all the characters of the

60
00:02:37,201 --> 00:02:39,500
input_expr one by one,

61
00:02:39,501 --> 00:02:41,300
therefore, I will need to convert the given

62
00:02:41,301 --> 00:02:43,400
string into vector of characters.

63
00:02:44,300 --> 00:02:46,600
The char function will be used for this purpose, and

64
00:02:46,601 --> 00:02:49,233
the result will be collected in a variable

65
00:02:49,234 --> 00:02:52,833
of input_char. The collect

66
00:02:52,834 --> 00:02:55,000
function converts the result to any

67
00:02:55,001 --> 00:02:57,433
collection type, such as vector of strings in this case.

68
00:02:58,600 --> 00:03:00,200
We will cover the same function in

69
00:03:00,201 --> 00:03:02,200
the later on sections of the course under the

70
00:03:02,201 --> 00:03:03,500
topic of Hydrators.

71
00:03:04,966 --> 00:03:05,833
For now, just note that

72
00:03:05,834 --> 00:03:08,700
it can be used to turn one collection into another.

73
00:03:10,100 --> 00:03:12,733
Next, I will use a for loop for

74
00:03:12,734 --> 00:03:14,433
iterating through each character in the

75
00:03:14,466 --> 00:03:16,766
input_char vector one by one.

76
00:03:16,767 --> 00:03:22,400
[No Audio]

77
00:03:22,401 --> 00:03:24,100
Inside the loop, I will first check if the

78
00:03:24,101 --> 00:03:27,100
character is an operand or operator. I will

79
00:03:27,101 --> 00:03:29,500
check if the character is not equal to one of

80
00:03:29,501 --> 00:03:33,200
the operator, that is, plus, minus, that is

81
00:03:33,400 --> 00:03:36,400
multiplication, divides and exponent.

82
00:03:37,100 --> 00:03:39,900
In case it is an operator, so I will add to the

83
00:03:39,901 --> 00:03:42,200
vector of strings, and in case it is not, then

84
00:03:42,201 --> 00:03:45,733
I will keep on iterating, until I find out the next operator.

85
00:03:46,766 --> 00:03:48,300
Let me add the code to check, if

86
00:03:48,301 --> 00:03:50,966
the input_char is an operator or not.

87
00:03:50,967 --> 00:04:02,800
[No Audio]

88
00:04:02,801 --> 00:04:05,133
In addition to operators, I will also check

89
00:04:05,134 --> 00:04:08,100
and add conditions, if it is an opening or

90
00:04:08,101 --> 00:04:09,866
closing parenthesis.

91
00:04:09,867 --> 00:04:13,000
[No Audio]

92
00:04:13,001 --> 00:04:13,833
Now let us move to the

93
00:04:13,834 --> 00:04:15,900
else part, which will mean that, none of the

94
00:04:15,901 --> 00:04:17,399
above conditions are being true, and

95
00:04:17,400 --> 00:04:19,800
therefore, the character does not corresponds

96
00:04:19,801 --> 00:04:23,500
to AND operator and neither it is

97
00:04:23,501 --> 00:04:26,533
opening or closing parenthesis. Since the

98
00:04:26,534 --> 00:04:29,100
operand can be of any length, as explained a

99
00:04:29,101 --> 00:04:32,000
little while ago, that is, it can consist of

100
00:04:32,001 --> 00:04:34,033
any number of digits, so therefore, I will

101
00:04:34,034 --> 00:04:36,533
keep on pushing this to a temp vector

102
00:04:36,534 --> 00:04:40,233
until I found a AND operator or parentheses.

103
00:04:41,900 --> 00:04:43,400
So outside the body of the loop,

104
00:04:43,401 --> 00:04:45,600
I will define a vector of chars called temp,

105
00:04:45,633 --> 00:04:48,166
and we'll initialize it as an empty vector.

106
00:04:48,167 --> 00:04:52,200
[No Audio]

107
00:04:52,201 --> 00:04:54,133
Inside the if statement, I will use it to

108
00:04:54,134 --> 00:04:56,133
store the character by pushing them into it.

109
00:04:56,134 --> 00:05:00,433
[No Audio]

110
00:05:00,434 --> 00:05:02,733
I will now grade the next character. And to do

111
00:05:02,734 --> 00:05:04,833
that, I will skip everything that is coming

112
00:05:04,834 --> 00:05:07,100
afterwards in the same loop, which can be

113
00:05:07,101 --> 00:05:09,300
done with the help of continue statement.

114
00:05:10,900 --> 00:05:13,600
This means now, that the temp will contain

115
00:05:13,601 --> 00:05:16,000
operands only. In summary, as long as the if

116
00:05:16,001 --> 00:05:18,200
part remains true, the temp will keep on

117
00:05:18,201 --> 00:05:20,500
accumulating all the characters or digit

118
00:05:20,501 --> 00:05:23,700
of a certain operand. Now let us code the else part.

119
00:05:24,233 --> 00:05:25,800
In the else part, I will first change

120
00:05:25,801 --> 00:05:27,333
the variable temp, which contains the

121
00:05:27,334 --> 00:05:30,000
individual characters in an operand, to that of

122
00:05:30,001 --> 00:05:32,333
a string, and then I will push it on to the

123
00:05:32,334 --> 00:05:34,833
tokenized_input. I will use the

124
00:05:34,834 --> 00:05:36,833
collect function which will collect all the

125
00:05:36,834 --> 00:05:39,500
individual characters in the variable temp as a string.

126
00:05:39,700 --> 00:05:42,300
And we'll add it as a single string

127
00:05:42,301 --> 00:05:45,133
element into the vector of tokenized_input.

128
00:05:45,134 --> 00:05:50,733
[No Audio]

129
00:05:50,734 --> 00:05:52,900
Next, I will also push the current character

130
00:05:52,901 --> 00:05:55,033
which is given by the variable i into the

131
00:05:55,034 --> 00:05:57,633
tokenized_input which corresponds

132
00:05:57,634 --> 00:05:58,733
to an operation.

133
00:05:58,734 --> 00:06:03,533
[No Audio]

134
00:06:03,534 --> 00:06:04,900
At the end, I will flush

135
00:06:04,901 --> 00:06:07,700
everything from the temp vector, because I am

136
00:06:07,701 --> 00:06:10,033
now expecting another operand, as the current

137
00:06:10,100 --> 00:06:12,900
operand has ended. This means that each time

138
00:06:12,901 --> 00:06:15,700
I encounter an operation, I will flush out

139
00:06:15,701 --> 00:06:18,500
the temp, since I am expecting another operand now.

140
00:06:18,501 --> 00:06:20,533
[No Audio]

141
00:06:20,534 --> 00:06:22,400
Okay outside the body of the loop, I

142
00:06:22,401 --> 00:06:24,400
will return the tokenized_input by

143
00:06:24,401 --> 00:06:26,266
writing tokenized_input.

144
00:06:27,500 --> 00:06:30,000
I will also add a print statement for displaying the

145
00:06:30,001 --> 00:06:31,000
tokenized_input.

146
00:06:31,001 --> 00:06:37,500
[No Audio]

147
00:06:37,501 --> 00:06:39,600
Let us call this function from the main now.

148
00:06:39,700 --> 00:06:42,800
I will store its result in a suitable variable.

149
00:06:42,801 --> 00:06:49,333
[No Audio]

150
00:06:49,334 --> 00:06:51,100
This program contains an error from

151
00:06:51,101 --> 00:06:53,900
computational perspective, which will

152
00:06:53,901 --> 00:06:56,266
become evident now, let us cargo run this.

153
00:06:56,267 --> 00:07:03,200
[No Audio]

154
00:07:03,201 --> 00:07:05,300
You may note, that it has converted the given

155
00:07:05,301 --> 00:07:07,633
expression correctly into individual tokens

156
00:07:07,634 --> 00:07:10,100
or strings contained in a string vector.

157
00:07:10,366 --> 00:07:12,533
The individual symbols are indicated by

158
00:07:12,534 --> 00:07:14,566
characters enclosed in double quotes.

159
00:07:14,666 --> 00:07:17,633
You may have spotted that the first symbol is

160
00:07:17,634 --> 00:07:20,100
empty, that is, there is nothing inside the

161
00:07:20,101 --> 00:07:22,400
double quotes which should have not happened.

162
00:07:22,466 --> 00:07:23,900
Let us see why this happened.

163
00:07:23,901 --> 00:07:25,933
[No Audio]

164
00:07:25,934 --> 00:07:29,000
For the first time when the loop starts, we have the symbol

165
00:07:29,001 --> 00:07:31,700
of opening parenthesis. So therefore, the

166
00:07:31,701 --> 00:07:33,900
else part will be executed, which means that,

167
00:07:33,901 --> 00:07:35,900
there is nothing in the temp and is empty.

168
00:07:36,300 --> 00:07:39,000
So pushing it onto the tokenized_input

169
00:07:39,001 --> 00:07:41,533
will lead to an empty string, and empty

170
00:07:41,534 --> 00:07:44,400
entry into the vector. To make this not to

171
00:07:44,401 --> 00:07:47,400
happen, we will add an if condition inside

172
00:07:47,401 --> 00:07:49,600
the else part, where we will check if the

173
00:07:49,601 --> 00:07:51,900
length of the temporary string variable is

174
00:07:51,901 --> 00:07:52,800
empty or not.

175
00:07:52,801 --> 00:07:56,700
[No Audio]

176
00:07:56,701 --> 00:07:58,700
We will just add the operator

177
00:07:58,701 --> 00:08:02,633
in this case, as there is no operand in this case to add.

178
00:08:02,634 --> 00:08:07,433
[No Audio]

179
00:08:07,434 --> 00:08:08,700
This will happen when we are

180
00:08:08,701 --> 00:08:11,300
processing the first symbol in the expression..

181
00:08:12,433 --> 00:08:15,033
And in the else part, we will do the

182
00:08:15,034 --> 00:08:16,933
processing as usual, so all the remaining

183
00:08:16,934 --> 00:08:18,900
statements will be added to the else part.

184
00:08:19,100 --> 00:08:20,766
Let me execute again.

185
00:08:20,767 --> 00:08:28,233
[No Audio]

186
00:08:28,234 --> 00:08:30,900
You may note that, this is working fine now.

187
00:08:31,733 --> 00:08:34,299
The expression that we were currently,

188
00:08:34,300 --> 00:08:37,466
considering, was ending at a closing parenthesis.

189
00:08:38,033 --> 00:08:39,900
Sometimes we may have

190
00:08:39,901 --> 00:08:42,500
expressions which may end in an operand, in

191
00:08:42,501 --> 00:08:44,500
this case the code will fail. For instance,

192
00:08:44,800 --> 00:08:46,600
let me change the input expression in the

193
00:08:46,601 --> 00:08:47,633
main function.

194
00:08:47,634 --> 00:08:50,233
[No Audio]

195
00:08:50,234 --> 00:08:51,733
Let us execute again now.

196
00:08:51,734 --> 00:08:58,000
[No Audio]

197
00:08:58,001 --> 00:08:59,633
You may note that, the symbols are being

198
00:08:59,700 --> 00:09:01,733
identified correctly, which are enclosed in

199
00:09:01,734 --> 00:09:04,133
double quotes. However, the last symbol has

200
00:09:04,134 --> 00:09:06,433
not been identified correctly, which has a

201
00:09:06,434 --> 00:09:09,600
value of 36. Let us see why this happened. I

202
00:09:09,601 --> 00:09:11,500
will copy the same expression, and we'll paste

203
00:09:11,501 --> 00:09:14,000
it as a comment, just before the start of the loop.

204
00:09:14,001 --> 00:09:17,600
[No Audio]

205
00:09:17,601 --> 00:09:19,900
Since there is an error in the

206
00:09:19,901 --> 00:09:22,400
last operand identification, so let us focus

207
00:09:22,401 --> 00:09:24,133
on what will happen inside the loop when we

208
00:09:24,134 --> 00:09:28,000
reach at the final operation. When the final

209
00:09:28,001 --> 00:09:30,400
operation is reached, which is a minus, so

210
00:09:30,401 --> 00:09:33,733
anything which has been found as operand,

211
00:09:33,833 --> 00:09:36,400
will be pushed onto the stack using the else part.

212
00:09:36,733 --> 00:09:38,500
The loop will then continue with the

213
00:09:38,501 --> 00:09:41,233
remaining characters, that is 3 and 6,

214
00:09:41,433 --> 00:09:43,800
and we'll push it on to the attempt variable.

215
00:09:45,000 --> 00:09:47,833
Now we never push them into the tokenized_input,

216
00:09:47,834 --> 00:09:49,500
so therefore they are

217
00:09:49,501 --> 00:09:51,800
not part of the tokenized_input.

218
00:09:52,200 --> 00:09:55,233
This means that our loop assumed that, we will

219
00:09:55,300 --> 00:09:58,800
always encounter an operand or closing or

220
00:09:58,801 --> 00:10:00,200
parenthesis at the end, which is

221
00:10:00,201 --> 00:10:02,900
not the case in this expression. To counter

222
00:10:02,901 --> 00:10:04,933
this, I will add one more if statement

223
00:10:04,934 --> 00:10:07,500
outside the body of the for loop. If there is

224
00:10:07,501 --> 00:10:09,500
something left, so I will push it on to the

225
00:10:09,501 --> 00:10:13,333
tokenized_input. This will ensure

226
00:10:13,334 --> 00:10:16,100
that if there is anything left in the temp,

227
00:10:16,101 --> 00:10:18,433
we will push it on to the tokenized_input.

228
00:10:18,700 --> 00:10:20,666
Let me execute once more.

229
00:10:20,667 --> 00:10:27,200
[No Audio]

230
00:10:27,201 --> 00:10:29,500
You may note that, yes, we have the last symbol

231
00:10:29,501 --> 00:10:32,600
also being detected successfully. To make

232
00:10:32,601 --> 00:10:35,000
the code look a bit better, I will run the

233
00:10:35,001 --> 00:10:37,500
command of cargo fmt, which will nicely

234
00:10:37,501 --> 00:10:38,733
format the code for us.

235
00:10:38,734 --> 00:10:44,033
[No Audio]

236
00:10:44,034 --> 00:10:46,300
The fmt is a nice and handy utility for

237
00:10:46,301 --> 00:10:49,033
formatting our code. Now that our code has

238
00:10:49,034 --> 00:10:51,133
been converted into individual symbols or

239
00:10:51,134 --> 00:10:53,200
tokens, we are now ready to implement the

240
00:10:53,201 --> 00:10:55,400
conversion to postfix and then expression

241
00:10:55,401 --> 00:10:58,500
evaluation from the postfix. We will cover

242
00:10:58,501 --> 00:11:00,300
that in the remaining of the

243
00:11:00,301 --> 00:11:02,100
implementation in the next tutorial.

244
00:11:02,600 --> 00:11:05,300
Do come back again, as the interesting part is yet to begin.

245
00:11:05,933 --> 00:11:08,300
Until next tutorial, happy Rust programming.

246
00:11:08,301 --> 00:11:15,400
[No Audio]