[No Audio]
Hello and welcome back again in the course.
In the previous tutorial, we looked at how to
convert a given expression to a postfix
expression. In this tutorial now, we will be
looking at how to evaluate the final result
from a postfix expression. Once we understand
the process, we will be in a better position
to implement the underlying algorithm in the
upcoming tutorial. As announced already, this
tutorial will be comparatively short. There
are two basic and simple rules that we need
to remember for converting a postfix
expression into an infix expression.
Again, we will be scanning a given expression from
left to right, and while doing so, the first
rule is that, if we encounter an operand, then
simply push it onto the stack. Let me write
this rule, so that we can easily remember it.
I will write if operand then push.
[No Audio]
The second rule is that, if we encounter an
operation, then pop up two elements from the
stack and perform the operations, and then
push the result back onto the stack.
Let me write this rule also. I will write if operation
then pop two elements and perform operation
and then push.
[No Audio]
Now, let us apply the two
rules on the expression that we have obtained
in postfix form from the previous tutorial.
I have written the expression already, and now
we will be scanning this expression from left
to right, and we'll apply the two rules on
each symbol that we encountered to evaluate
the final result. For ease of work, I have
already made a table with two columns
indicating the symbols and the stack.
The first symbol in the expression is an operand.
So under the symbol, I will write 33. Since it
is an operand, so therefore we will push it
onto the stack. The next symbol is 45. It is
again an operand, so I will push it onto the
stack by writing the already contained
element of 33 followed by 45 under the stack column.
Please note that the top of the stack
in this case, is indicated by the element at
the right most position, and the stack is in
horizontal direction. The next symbol is
3, which is operand, and we'll add
it to the stack. So under the stack, I will
write the updated status of stack. The
next symbol is divides. Since this is an
operation, so therefore we will pop up two
elements from the stack, and we'll perform the
operation on it. Please note that the element
which is popped first, will be our second
operand, and element which is being popped up
second, will be our first operand. This means
that in this case the value of three will be
popped first, which is going to be the second operand.
[No Audio]
Next, the value of 45 will be popped,
which is going to be our first operand.
Let me also draw it.
[No Audio]
Finally, we will do the
operation of divides, which will be operand1
divided by operand 2. So let me
indicate this by writing, op1/op2 = 45/3.
The result of this division which has a value
of 15, will be pushed onto the stack. So under
the stack, I will indicate the new status of
the stack. The next symbol is 2, which is
operand, so we will push it on to the stack.
Let me update the symbol and the stack
columns accordingly.
The next symbol is 9,
which is operand, so we will push it on to the stack.
Let me update the symbol and the stack
columns again. Next, we have the symbol of
addition, this is an operation. So again, we
will be popping up the two elements, and we'll
perform the operations on them, and the result
will be pushed back onto the stack. In this
case, we will pop 9 and 2, and we'll add them.
The result of addition which is 11, will be
pushed onto the stack. So let me update the
status of the stack.
[No Audio]
Next we have multiplication operation, so let me write it
under symbol. Again, we will be popping two
elements and we'll perform the operation on them.
In this case, the value of 11 and 15
will be popped, and will be multiplied
together, resulting in a value of 165, which
will, which will be pushed onto the stack.
So let me update the status of the stack.
[No Audio]
Next is the addition symbol, so let me write it.
Again, we will be popping two elements which
are 165 and 33 in this case, and we will add
them together, which will result in a value of
198, which will be pushed onto the stack.
So, let me update the status of the stack again.
[No Audio]
Next, is the symbol of 50, which will be pushed
onto the stack. So, let me update the status.
[No Audio]
Finally, we have the symbol indicating the
subtraction operation. Again the two elements
will be popped. Please note again the element
which is popped first is going to be the
second operand, and the element which is
popped a second, will be the first operand.
So, I will do op1- op2,
that is 198 - 50, resulting in a value of 148
which will be pushed back onto the stack.
Now, when there is no more symbols to scan,
then anything which is left behind in the
stack is being popped out. And that is the
final answer, which in this case has a value of 148.
Okay, let us quickly check if we have
computed the result correctly or not. I have
already written the original expression. In
maths, when we have an expression like this
one, we will first compute anything which is
inside the parentheses. If there are more
than one operation inside the parentheses,
then we will apply the operation precedence
rule, according to which the divides has the
highest precedence, followed by multiplication,
followed by addition, and finally subtraction.
So, in this case, the value of 2 + 9
will be first computed, resulting in a value of 11.
So, I will write the simplified expression again.
Next inside the outer
brackets, there are many operations. So we
will apply the operation precedence according
to which the divides has the highest priority.
So, we will divide 45/3 which has a value of 15.
Next, we will do the
multiplication operation, because it has the
highest precedence. So let me write the updated expression.
[No Audio]
Next, we will perform the addition, which will
result in a value of 198. Let me write new updated expression.
Finally, when we will do
the subtraction operation, which will result
in a value of 148. You may have noted, that we
have computed the value of 148 in our
example, which confirms that our result is correct.
Okay, great. Now in the next
tutorial, we will be looking at the
implementation details of Expression
Evaluation in Rust. That is going to be fun
and interesting. So do come back for learning
that, and until next tutorial, happy Rust programming.
[No Audio]