1
00:00:00,000 --> 00:00:06,466
[No Audio]

2
00:00:06,467 --> 00:00:08,666
Hello and welcome back again in the course.

3
00:00:08,866 --> 00:00:11,566
In this, and some of the upcoming videos, we

4
00:00:11,567 --> 00:00:13,800
will be looking at another interesting

5
00:00:13,833 --> 00:00:17,266
application of stacks, called Expression Evaluation.

6
00:00:18,866 --> 00:00:20,800
We will first, explain the

7
00:00:20,801 --> 00:00:23,333
procedure or algorithm for Expression

8
00:00:23,366 --> 00:00:25,800
Evaluation, and then we will come back to its

9
00:00:25,801 --> 00:00:28,600
implementation in Rust in the later on videos.

10
00:00:29,366 --> 00:00:31,800
This is important, because if we do

11
00:00:31,801 --> 00:00:34,800
not understand the procedure well, then we

12
00:00:34,801 --> 00:00:37,366
will not be able to implement it correctly.

13
00:00:37,866 --> 00:00:40,666
Again, the idea will be to use the concepts,

14
00:00:40,667 --> 00:00:42,933
that we have learned so far in the course,

15
00:00:43,333 --> 00:00:47,000
and do not introduce any advanced level topic for now.

16
00:00:47,700 --> 00:00:49,633
With this let's start learning

17
00:00:49,666 --> 00:00:53,100
Expression Evaluation. There are many ways in

18
00:00:53,101 --> 00:00:55,100
which the mathematical expressions can be

19
00:00:55,101 --> 00:00:58,766
evaluated. The method I am going to use is, to

20
00:00:58,767 --> 00:01:01,333
first convert the given expression into a

21
00:01:01,334 --> 00:01:05,000
postfix expression, and then using the postfix

22
00:01:05,033 --> 00:01:08,333
expression, we will evaluate the original

23
00:01:08,334 --> 00:01:11,733
expression. This means that, there will be two

24
00:01:11,734 --> 00:01:14,966
major steps in our procedure. First, we will

25
00:01:14,967 --> 00:01:17,166
convert the given mathematical expression

26
00:01:17,167 --> 00:01:20,333
into a postfix expression, and then we will

27
00:01:20,334 --> 00:01:22,900
use the postfix expression to compute or

28
00:01:22,901 --> 00:01:25,800
evaluate the given expression. While doing

29
00:01:25,801 --> 00:01:28,133
this problem, we will have a chance of

30
00:01:28,134 --> 00:01:31,633
applying what we have learned so far in the course.

31
00:01:32,800 --> 00:01:34,400
We will start with a postfix

32
00:01:34,433 --> 00:01:36,766
expression. A mathematical expression

33
00:01:36,767 --> 00:01:39,600
consists of operands and operators. The

34
00:01:39,633 --> 00:01:43,333
operands are variables or constants, constant

35
00:01:43,334 --> 00:01:45,933
values that we used inside an expression, such

36
00:01:45,934 --> 00:01:50,633
as abc, or xyz, or constant values such as 33,

37
00:01:50,634 --> 00:01:55,233
-5, 9, etc. The operators are

38
00:01:55,266 --> 00:01:58,266
operations, such as multiplication, division,

39
00:01:58,300 --> 00:02:00,933
addition, subtraction, exponent, etc.

40
00:02:02,000 --> 00:02:05,433
Now, given the operands and operators, a postfix

41
00:02:05,466 --> 00:02:07,900
expression is a collection of operators and

42
00:02:07,933 --> 00:02:10,765
operators, in which the operator is placed

43
00:02:10,766 --> 00:02:14,833
after the operands. That means, in a postfix

44
00:02:14,834 --> 00:02:17,533
expression, the operator follows the operand.

45
00:02:18,000 --> 00:02:20,833
For instance, if we have an expression like a + b,

46
00:02:21,066 --> 00:02:22,800
then the postfix expression

47
00:02:22,801 --> 00:02:26,166
corresponding to this would be a b +.

48
00:02:26,966 --> 00:02:30,100
Of course if the expression grows, the postfix

49
00:02:30,133 --> 00:02:32,566
expression would be a bit different from this.

50
00:02:32,700 --> 00:02:34,866
The mathematical expressions that we

51
00:02:35,133 --> 00:02:38,466
generally see, such as a + b are also known

52
00:02:38,467 --> 00:02:42,566
to be in infix form. So to begin with, we

53
00:02:42,567 --> 00:02:44,833
will first look at how to convert a given

54
00:02:44,834 --> 00:02:47,800
mathematical expression into a postfix form.

55
00:02:48,633 --> 00:02:51,633
For the conversion to postfix expression, we

56
00:02:51,634 --> 00:02:54,233
need to follow certain rules. Let us look at

57
00:02:54,234 --> 00:02:56,300
these rules one by one.

58
00:02:57,533 --> 00:03:01,766
The first rule is related to the priorities of the operators.

59
00:03:03,566 --> 00:03:06,922
The operators of addition and subtraction has

60
00:03:06,923 --> 00:03:10,355
the lowest priority. Since I have written

61
00:03:10,366 --> 00:03:13,366
about the operators together, this means that

62
00:03:13,400 --> 00:03:16,200
they have equal priority. Next in the

63
00:03:16,201 --> 00:03:18,966
priority level comes the operators of

64
00:03:18,967 --> 00:03:21,700
multiplication and division. Finally, the

65
00:03:21,701 --> 00:03:24,866
exponent has the highest priority. The second

66
00:03:24,867 --> 00:03:27,600
rule is a bit long, so let me write it and

67
00:03:27,601 --> 00:03:30,633
then I will explain it. If the scanned operator

68
00:03:30,634 --> 00:03:34,200
is equal, is less than or equal to the top of

69
00:03:34,201 --> 00:03:37,500
the stack in priority, then we will pop the

70
00:03:37,501 --> 00:03:41,800
operators until we have a low priority operator.

71
00:03:42,966 --> 00:03:44,666
The pop elements will be added to

72
00:03:44,667 --> 00:03:46,033
the postfix expression.

73
00:03:46,034 --> 00:03:49,112
[No Audio]

74
00:03:49,113 --> 00:03:50,600
What happens during the algorithm

75
00:03:50,601 --> 00:03:52,066
is that, we will be scanning the

76
00:03:52,067 --> 00:03:54,566
expression from left to right, and we will

77
00:03:54,567 --> 00:03:56,833
add elements to the stack one by one.

78
00:03:56,834 --> 00:04:00,633
So if we scan an operator, whose priority is equal

79
00:04:00,634 --> 00:04:03,333
to or less than the priority of the top of

80
00:04:03,334 --> 00:04:06,300
the stack, then we will pop elements from the

81
00:04:06,301 --> 00:04:09,066
stack until the top of the stack has lesser

82
00:04:09,067 --> 00:04:11,533
priority than the scanned character.

83
00:04:12,000 --> 00:04:14,933
All the popped elements will be added to the postfix

84
00:04:14,934 --> 00:04:17,433
expression. When this position is reached,

85
00:04:17,466 --> 00:04:20,966
then we will push the scanned operator onto the stack.

86
00:04:22,266 --> 00:04:24,300
The next rule is that, if we have an

87
00:04:24,333 --> 00:04:28,000
opening parenthesis, then we will just add it

88
00:04:28,001 --> 00:04:31,133
to the stack. The next rule is also very simple.

89
00:04:32,133 --> 00:04:34,500
This rule is that, when we have a

90
00:04:34,501 --> 00:04:38,466
closing parenthesis, then a pop element until

91
00:04:38,467 --> 00:04:40,733
you reach the opening parenthesis.

92
00:04:40,734 --> 00:04:45,200
[No Audio]

93
00:04:45,201 --> 00:04:47,900
At this stage, we will discard both the parenthesis

94
00:04:47,901 --> 00:04:50,766
and add the pop elements to the postfix expression.

95
00:04:51,166 --> 00:04:52,666
The parentheses themselves will

96
00:04:52,667 --> 00:04:54,900
not be added to the postfix expression.

97
00:04:56,200 --> 00:04:59,000
The final rule is that, if we have an operand,

98
00:04:59,001 --> 00:05:01,633
we will just add it to the postfix expression.

99
00:05:03,000 --> 00:05:05,300
There are some minor rules also, but we will

100
00:05:05,301 --> 00:05:08,033
not write them here and we will explain them

101
00:05:08,034 --> 00:05:11,033
when we discuss the example. For now, let us

102
00:05:11,034 --> 00:05:13,133
stick to these basic rules and the minor

103
00:05:13,134 --> 00:05:15,966
rules will become clear to us during the example.

104
00:05:17,233 --> 00:05:19,833
Okay with these rules, we are now

105
00:05:19,834 --> 00:05:22,133
ready to see an example of how to convert an

106
00:05:22,134 --> 00:05:25,433
infix expression into a postfix expression.

107
00:05:26,133 --> 00:05:28,566
Before starting the example, let us revise

108
00:05:28,567 --> 00:05:30,900
quickly the rules, so that we, so that they

109
00:05:30,901 --> 00:05:33,466
remain fresh in our mind during the example.

110
00:05:33,966 --> 00:05:36,433
The first rule is related to the priorities,

111
00:05:36,466 --> 00:05:39,400
which says that the operation of, the two or

112
00:05:39,401 --> 00:05:41,966
three operations of addition and subtraction

113
00:05:41,967 --> 00:05:45,300
has the least priority. Next in the priority

114
00:05:45,301 --> 00:05:47,533
level are the operators of multiplication and

115
00:05:47,534 --> 00:05:50,433
division. And finally, the exponent has the

116
00:05:50,434 --> 00:05:54,433
highest priority. The second rule is that, the

117
00:05:54,434 --> 00:05:57,300
scanned operator will be checked against the top

118
00:05:57,301 --> 00:06:00,666
of the stack, and if the scanned operator is lesser

119
00:06:00,667 --> 00:06:03,333
than than or equal to in priority compared to

120
00:06:03,334 --> 00:06:06,200
the top of the stack, then we will be popping

121
00:06:06,233 --> 00:06:08,666
elements from the stack, until we reach an

122
00:06:08,667 --> 00:06:10,833
operator at the top of the stack, which is

123
00:06:10,834 --> 00:06:14,300
strictly lesser in priority than the scanned operator.

124
00:06:15,566 --> 00:06:17,500
The third rule is with regards to

125
00:06:17,501 --> 00:06:19,933
the opening parenthesis, which says that, we

126
00:06:19,934 --> 00:06:23,866
will just push it to the start. Whenever we

127
00:06:23,867 --> 00:06:25,966
found a closing parenthesis, then we will pop

128
00:06:25,967 --> 00:06:28,400
elements until we reach the opening parenthesis.

129
00:06:29,800 --> 00:06:31,433
The final rule is that, if we

130
00:06:31,434 --> 00:06:33,966
have an operand, we will just add it to the

131
00:06:33,967 --> 00:06:35,300
postfix expression.

132
00:06:36,135 --> 00:06:37,300
There is also one

133
00:06:37,301 --> 00:06:39,666
additional rule, and that is, if there is

134
00:06:39,667 --> 00:06:41,400
something left in the stack, then we will

135
00:06:41,401 --> 00:06:44,766
just pop and add it to the postfix expression

136
00:06:44,800 --> 00:06:47,833
until it becomes empty. With this, we will

137
00:06:47,834 --> 00:06:50,100
start with an example, where the details of

138
00:06:50,101 --> 00:06:52,066
the whole process will become evident and

139
00:06:52,100 --> 00:06:54,733
easy to understand. So, let us start with an example.

140
00:06:56,066 --> 00:06:59,100
In this example, I am considering this expression.

141
00:06:59,766 --> 00:07:01,166
To show the complete working,

142
00:07:01,381 --> 00:07:03,648
I have created a table with three columns.

143
00:07:04,500 --> 00:07:08,200
The first column represents the symbols, which

144
00:07:08,201 --> 00:07:11,266
will be the individual items or elements in

145
00:07:11,267 --> 00:07:14,133
the expression, and can be either an operand,

146
00:07:14,166 --> 00:07:18,166
or operator, or parentheses. The second column

147
00:07:18,167 --> 00:07:20,633
is the stack, and the third column will be the

148
00:07:20,634 --> 00:07:24,000
postfix expression. The expression will be

149
00:07:24,001 --> 00:07:25,266
scanned from left to right.

150
00:07:26,505 --> 00:07:27,766
So, first the symbol

151
00:07:27,767 --> 00:07:30,200
of opening parenthesis will be evaluated.

152
00:07:30,766 --> 00:07:32,266
Since the top of the stack is

153
00:07:32,267 --> 00:07:35,300
empty, therefore, we will just push it onto the stack.

154
00:07:35,800 --> 00:07:37,733
So under the symbol, I will write

155
00:07:37,734 --> 00:07:40,066
opening parenthesis, and under the stack, I

156
00:07:40,067 --> 00:07:42,100
will answer write opening parenthesis.

157
00:07:42,633 --> 00:07:45,000
As pointed out in the rules, the opening and

158
00:07:45,001 --> 00:07:47,666
closing parentheses are never

159
00:07:47,667 --> 00:07:50,133
part of the postfix expression. Therefore, we

160
00:07:50,134 --> 00:07:53,400
will not write anything under the postfix column.

161
00:07:54,466 --> 00:07:57,533
Next, we have the symbol of 33. Since

162
00:07:57,566 --> 00:08:00,200
it is an operand, so we will add it to the

163
00:08:00,201 --> 00:08:03,266
postfix expression and nothing happens to the stack.

164
00:08:03,267 --> 00:08:05,800
Let me quickly write the new stats

165
00:08:05,801 --> 00:08:09,066
under the three columns. The next symbol is a

166
00:08:09,067 --> 00:08:12,133
plus operator. Please note that, although, we

167
00:08:12,134 --> 00:08:14,966
do not define the priority of the opening

168
00:08:14,967 --> 00:08:18,066
parenthesis, but remember that since it is

169
00:08:18,067 --> 00:08:21,033
not an operator, so if we compare it with an

170
00:08:21,034 --> 00:08:23,200
operator, so the opening parenthesis is

171
00:08:23,201 --> 00:08:25,000
going to have the least priority when

172
00:08:25,001 --> 00:08:28,200
compared to any of the operator. So, now in

173
00:08:28,201 --> 00:08:30,600
this case, we will just push the plus

174
00:08:30,601 --> 00:08:32,799
operator onto the stack because a least

175
00:08:32,800 --> 00:08:36,299
priority symbol exist. So, let me update the

176
00:08:36,300 --> 00:08:37,765
states accordingly.

177
00:08:39,299 --> 00:08:42,200
Next, we have the operand of 45.

178
00:08:42,433 --> 00:08:44,866
In case of operands, we just add it to

179
00:08:44,867 --> 00:08:47,933
the postfix expression. So let me update the columns.

180
00:08:47,934 --> 00:08:53,133
[No Audio]

181
00:08:53,134 --> 00:08:55,566
Next we have the operator of divide. Since

182
00:08:55,567 --> 00:08:58,300
divide operator has a greater priority, so we

183
00:08:58,301 --> 00:08:59,700
will add it to the stack.

184
00:09:00,566 --> 00:09:02,700
Let me update the columns.

185
00:09:02,701 --> 00:09:07,866
[No Audio]

186
00:09:07,867 --> 00:09:10,600
Next we have an operand of three. So we will

187
00:09:10,601 --> 00:09:13,400
just add it to the postfix expression, let me

188
00:09:13,401 --> 00:09:15,000
update the columns again.

189
00:09:15,001 --> 00:09:19,700
[No Audio]

190
00:09:19,701 --> 00:09:22,233
Next, we have the operator of multiplication.

191
00:09:22,234 --> 00:09:24,300
Now in this case the operation, which is

192
00:09:24,301 --> 00:09:27,000
currently being scanned, is lesser than or

193
00:09:27,001 --> 00:09:29,200
equal to in priority than the top of the

194
00:09:29,201 --> 00:09:31,966
stack. So therefore, we will pop up at the

195
00:09:31,967 --> 00:09:34,933
top of the stack, until the top of the stack

196
00:09:34,934 --> 00:09:38,500
has lesser priority then that of multiplication.

197
00:09:40,000 --> 00:09:41,400
So therefore, the divides

198
00:09:41,401 --> 00:09:43,466
will be first popped out from the top of the

199
00:09:43,467 --> 00:09:46,433
stack, and will be added to the postfix expression.

200
00:09:48,100 --> 00:09:49,966
Let me add it to the postfix expression.

201
00:09:51,566 --> 00:09:53,400
When the divide is popped out, the

202
00:09:53,401 --> 00:09:56,166
top of the stack becomes plus, which has

203
00:09:56,167 --> 00:09:59,466
lesser priority and therefore we can

204
00:09:59,467 --> 00:10:01,566
now add the multiplication to the top of

205
00:10:01,567 --> 00:10:04,100
the stack. So, let me update the columns.

206
00:10:04,101 --> 00:10:09,066
[No Audio]

207
00:10:09,067 --> 00:10:12,600
Next we have opening parenthesis. So, we will just

208
00:10:12,601 --> 00:10:17,000
add to the stack. This is because the rule

209
00:10:17,001 --> 00:10:19,200
says that, when we encountered an opening

210
00:10:19,201 --> 00:10:22,500
parenthesis, then we are just going to push

211
00:10:22,501 --> 00:10:24,733
it onto the stack, and we are not going to do

212
00:10:24,734 --> 00:10:25,833
any comparisons.

213
00:10:25,834 --> 00:10:27,784
[No Audio]

214
00:10:27,785 --> 00:10:29,110
Let me add the columns.

215
00:10:29,111 --> 00:10:34,200
[No Audio]

216
00:10:34,201 --> 00:10:36,600
Next, we have an operand of two, which will be

217
00:10:36,601 --> 00:10:39,500
added to the postfix expression. So, let me

218
00:10:39,501 --> 00:10:40,757
update the columns again.

219
00:10:40,758 --> 00:10:46,100
[No Audio]

220
00:10:46,101 --> 00:10:48,500
Next is the operator of plus. In this case, it

221
00:10:48,501 --> 00:10:50,200
will be checked with the top of the stack

222
00:10:50,201 --> 00:10:52,000
which is an opening parenthesis.

223
00:10:52,001 --> 00:10:54,900
The operators are now checked against the

224
00:10:54,901 --> 00:10:57,466
opening parenthesis, or more precisely, we can

225
00:10:57,467 --> 00:10:59,400
say that the operations will have higher

226
00:10:59,401 --> 00:11:01,666
precedence over the opening parenthesis.

227
00:11:01,800 --> 00:11:05,733
So therefore, the addition will be added to the stack.

228
00:11:05,734 --> 00:11:07,566
Let me update the columns again.

229
00:11:07,576 --> 00:11:09,900
[No Audio]

230
00:11:09,901 --> 00:11:12,633
Next, we have the operand of 9,

231
00:11:12,634 --> 00:11:15,066
which will be simply added to the postfix

232
00:11:15,067 --> 00:11:17,446
expression. Let me update quickly again.

233
00:11:17,447 --> 00:11:20,033
[No Audio]

234
00:11:20,034 --> 00:11:22,800
Next, we have the closing parenthesis. The

235
00:11:22,801 --> 00:11:24,800
rule says that, whenever we encounter the

236
00:11:24,801 --> 00:11:27,000
closing parenthesis, then we will pop up

237
00:11:27,033 --> 00:11:29,433
elements from the stack, until we reach the

238
00:11:29,434 --> 00:11:32,233
opening parenthesis. All the popped elements

239
00:11:32,234 --> 00:11:34,800
will be added to the postfix, and the opening and

240
00:11:34,801 --> 00:11:37,600
closing parenthesis are not part of the

241
00:11:37,601 --> 00:11:41,076
expression. Let me update the columns accordingly.

242
00:11:41,077 --> 00:11:45,466
[No Audio]

243
00:11:45,467 --> 00:11:47,400
Next we have the operation of

244
00:11:47,666 --> 00:11:50,633
subtraction. This will be compared against the

245
00:11:50,634 --> 00:11:53,100
top of the stack. In this case, since the

246
00:11:53,300 --> 00:11:55,900
subtraction has lesser priority compared to

247
00:11:55,901 --> 00:11:58,466
the top of the stack. Therefore, we will pop

248
00:11:58,467 --> 00:12:01,166
up elements until the subtraction has greater

249
00:12:01,167 --> 00:12:03,133
priority than the top of the stack.

250
00:12:03,366 --> 00:12:06,766
So the operations of multiplication and addition

251
00:12:06,900 --> 00:12:10,466
will be popped up, and it will be added to the

252
00:12:10,467 --> 00:12:12,833
postfix, and then finally we will push the

253
00:12:12,834 --> 00:12:14,766
subtraction operation to the stack.

254
00:12:14,900 --> 00:12:16,600
So let me update the columns.

255
00:12:16,601 --> 00:12:21,213
[No Audio]

256
00:12:21,214 --> 00:12:22,933
Next we have an operand of 50,

257
00:12:22,934 --> 00:12:26,208
which will be added to the postfix, let me update again.

258
00:12:26,209 --> 00:12:30,000
[No Audio]

259
00:12:30,001 --> 00:12:31,500
Finally, we have the closing

260
00:12:31,501 --> 00:12:33,433
parenthesis. Now in case of closing

261
00:12:33,434 --> 00:12:35,533
parenthesis, we are going to pop elements

262
00:12:35,566 --> 00:12:37,933
until we encountered the opening parenthesis.

263
00:12:38,200 --> 00:12:40,252
So let me update the columns accordingly.

264
00:12:40,253 --> 00:12:45,100
[No Audio]

265
00:12:45,101 --> 00:12:48,333
You may note that this leaves the stack empty and

266
00:12:48,366 --> 00:12:51,600
also ends the expression. The final step is

267
00:12:51,601 --> 00:12:53,733
to pop up anything that is being left in the

268
00:12:53,734 --> 00:12:56,766
stack. But since stack is empty, therefore we

269
00:12:56,767 --> 00:13:00,666
do not have anything left over. This is the

270
00:13:00,667 --> 00:13:03,333
corresponding expression in postfix form.

271
00:13:04,166 --> 00:13:06,000
Okay, that brings us to the end of this

272
00:13:06,001 --> 00:13:08,200
tutorial. In the next tutorial, we will be

273
00:13:08,201 --> 00:13:11,033
looking at how we can use the postfix

274
00:13:11,034 --> 00:13:13,300
expression to evaluate the final result of

275
00:13:13,301 --> 00:13:15,766
the expression. I know you guys will be

276
00:13:15,767 --> 00:13:18,033
waiting for the implementation part, but I

277
00:13:18,034 --> 00:13:20,166
promise the next tutorial will be short and

278
00:13:20,167 --> 00:13:22,933
quick, because we already did the hard part.

279
00:13:23,033 --> 00:13:25,800
So do come back to cover that, and until next tutorial.

280
00:13:25,801 --> 00:13:27,700
enjoy Rust programming.

281
00:13:27,701 --> 00:13:33,566
[No Audio]