[No Audio]
Hello and welcome back again in the course.
In this, and some of the upcoming videos, we
will be looking at another interesting
application of stacks, called Expression Evaluation.
We will first, explain the
procedure or algorithm for Expression
Evaluation, and then we will come back to its
implementation in Rust in the later on videos.
This is important, because if we do
not understand the procedure well, then we
will not be able to implement it correctly.
Again, the idea will be to use the concepts,
that we have learned so far in the course,
and do not introduce any advanced level topic for now.
With this let's start learning
Expression Evaluation. There are many ways in
which the mathematical expressions can be
evaluated. The method I am going to use is, to
first convert the given expression into a
postfix expression, and then using the postfix
expression, we will evaluate the original
expression. This means that, there will be two
major steps in our procedure. First, we will
convert the given mathematical expression
into a postfix expression, and then we will
use the postfix expression to compute or
evaluate the given expression. While doing
this problem, we will have a chance of
applying what we have learned so far in the course.
We will start with a postfix
expression. A mathematical expression
consists of operands and operators. The
operands are variables or constants, constant
values that we used inside an expression, such
as abc, or xyz, or constant values such as 33,
-5, 9, etc. The operators are
operations, such as multiplication, division,
addition, subtraction, exponent, etc.
Now, given the operands and operators, a postfix
expression is a collection of operators and
operators, in which the operator is placed
after the operands. That means, in a postfix
expression, the operator follows the operand.
For instance, if we have an expression like a + b,
then the postfix expression
corresponding to this would be a b +.
Of course if the expression grows, the postfix
expression would be a bit different from this.
The mathematical expressions that we
generally see, such as a + b are also known
to be in infix form. So to begin with, we
will first look at how to convert a given
mathematical expression into a postfix form.
For the conversion to postfix expression, we
need to follow certain rules. Let us look at
these rules one by one.
The first rule is related to the priorities of the operators.
The operators of addition and subtraction has
the lowest priority. Since I have written
about the operators together, this means that
they have equal priority. Next in the
priority level comes the operators of
multiplication and division. Finally, the
exponent has the highest priority. The second
rule is a bit long, so let me write it and
then I will explain it. If the scanned operator
is equal, is less than or equal to the top of
the stack in priority, then we will pop the
operators until we have a low priority operator.
The pop elements will be added to
the postfix expression.
[No Audio]
What happens during the algorithm
is that, we will be scanning the
expression from left to right, and we will
add elements to the stack one by one.
So if we scan an operator, whose priority is equal
to or less than the priority of the top of
the stack, then we will pop elements from the
stack until the top of the stack has lesser
priority than the scanned character.
All the popped elements will be added to the postfix
expression. When this position is reached,
then we will push the scanned operator onto the stack.
The next rule is that, if we have an
opening parenthesis, then we will just add it
to the stack. The next rule is also very simple.
This rule is that, when we have a
closing parenthesis, then a pop element until
you reach the opening parenthesis.
[No Audio]
At this stage, we will discard both the parenthesis
and add the pop elements to the postfix expression.
The parentheses themselves will
not be added to the postfix expression.
The final rule is that, if we have an operand,
we will just add it to the postfix expression.
There are some minor rules also, but we will
not write them here and we will explain them
when we discuss the example. For now, let us
stick to these basic rules and the minor
rules will become clear to us during the example.
Okay with these rules, we are now
ready to see an example of how to convert an
infix expression into a postfix expression.
Before starting the example, let us revise
quickly the rules, so that we, so that they
remain fresh in our mind during the example.
The first rule is related to the priorities,
which says that the operation of, the two or
three operations of addition and subtraction
has the least priority. Next in the priority
level are the operators of multiplication and
division. And finally, the exponent has the
highest priority. The second rule is that, the
scanned operator will be checked against the top
of the stack, and if the scanned operator is lesser
than than or equal to in priority compared to
the top of the stack, then we will be popping
elements from the stack, until we reach an
operator at the top of the stack, which is
strictly lesser in priority than the scanned operator.
The third rule is with regards to
the opening parenthesis, which says that, we
will just push it to the start. Whenever we
found a closing parenthesis, then we will pop
elements until we reach the opening parenthesis.
The final rule is that, if we
have an operand, we will just add it to the
postfix expression.
There is also one
additional rule, and that is, if there is
something left in the stack, then we will
just pop and add it to the postfix expression
until it becomes empty. With this, we will
start with an example, where the details of
the whole process will become evident and
easy to understand. So, let us start with an example.
In this example, I am considering this expression.
To show the complete working,
I have created a table with three columns.
The first column represents the symbols, which
will be the individual items or elements in
the expression, and can be either an operand,
or operator, or parentheses. The second column
is the stack, and the third column will be the
postfix expression. The expression will be
scanned from left to right.
So, first the symbol
of opening parenthesis will be evaluated.
Since the top of the stack is
empty, therefore, we will just push it onto the stack.
So under the symbol, I will write
opening parenthesis, and under the stack, I
will answer write opening parenthesis.
As pointed out in the rules, the opening and
closing parentheses are never
part of the postfix expression. Therefore, we
will not write anything under the postfix column.
Next, we have the symbol of 33. Since
it is an operand, so we will add it to the
postfix expression and nothing happens to the stack.
Let me quickly write the new stats
under the three columns. The next symbol is a
plus operator. Please note that, although, we
do not define the priority of the opening
parenthesis, but remember that since it is
not an operator, so if we compare it with an
operator, so the opening parenthesis is
going to have the least priority when
compared to any of the operator. So, now in
this case, we will just push the plus
operator onto the stack because a least
priority symbol exist. So, let me update the
states accordingly.
Next, we have the operand of 45.
In case of operands, we just add it to
the postfix expression. So let me update the columns.
[No Audio]
Next we have the operator of divide. Since
divide operator has a greater priority, so we
will add it to the stack.
Let me update the columns.
[No Audio]
Next we have an operand of three. So we will
just add it to the postfix expression, let me
update the columns again.
[No Audio]
Next, we have the operator of multiplication.
Now in this case the operation, which is
currently being scanned, is lesser than or
equal to in priority than the top of the
stack. So therefore, we will pop up at the
top of the stack, until the top of the stack
has lesser priority then that of multiplication.
So therefore, the divides
will be first popped out from the top of the
stack, and will be added to the postfix expression.
Let me add it to the postfix expression.
When the divide is popped out, the
top of the stack becomes plus, which has
lesser priority and therefore we can
now add the multiplication to the top of
the stack. So, let me update the columns.
[No Audio]
Next we have opening parenthesis. So, we will just
add to the stack. This is because the rule
says that, when we encountered an opening
parenthesis, then we are just going to push
it onto the stack, and we are not going to do
any comparisons.
[No Audio]
Let me add the columns.
[No Audio]
Next, we have an operand of two, which will be
added to the postfix expression. So, let me
update the columns again.
[No Audio]
Next is the operator of plus. In this case, it
will be checked with the top of the stack
which is an opening parenthesis.
The operators are now checked against the
opening parenthesis, or more precisely, we can
say that the operations will have higher
precedence over the opening parenthesis.
So therefore, the addition will be added to the stack.
Let me update the columns again.
[No Audio]
Next, we have the operand of 9,
which will be simply added to the postfix
expression. Let me update quickly again.
[No Audio]
Next, we have the closing parenthesis. The
rule says that, whenever we encounter the
closing parenthesis, then we will pop up
elements from the stack, until we reach the
opening parenthesis. All the popped elements
will be added to the postfix, and the opening and
closing parenthesis are not part of the
expression. Let me update the columns accordingly.
[No Audio]
Next we have the operation of
subtraction. This will be compared against the
top of the stack. In this case, since the
subtraction has lesser priority compared to
the top of the stack. Therefore, we will pop
up elements until the subtraction has greater
priority than the top of the stack.
So the operations of multiplication and addition
will be popped up, and it will be added to the
postfix, and then finally we will push the
subtraction operation to the stack.
So let me update the columns.
[No Audio]
Next we have an operand of 50,
which will be added to the postfix, let me update again.
[No Audio]
Finally, we have the closing
parenthesis. Now in case of closing
parenthesis, we are going to pop elements
until we encountered the opening parenthesis.
So let me update the columns accordingly.
[No Audio]
You may note that this leaves the stack empty and
also ends the expression. The final step is
to pop up anything that is being left in the
stack. But since stack is empty, therefore we
do not have anything left over. This is the
corresponding expression in postfix form.
Okay, that brings us to the end of this
tutorial. In the next tutorial, we will be
looking at how we can use the postfix
expression to evaluate the final result of
the expression. I know you guys will be
waiting for the implementation part, but I
promise the next tutorial will be short and
quick, because we already did the hard part.
So do come back to cover that, and until next tutorial.
enjoy Rust programming.
[No Audio]