[No Audio]
Hello and welcome back again. Finally the
wait is over, and in this tutorial we will be
implementing the conversion to postfix.
I am starting with the same script, that we wrote
in the last tutorial. Before starting to
code, it will be useful to have a look at the
rules for conversion to postfix.
[No Audio]
The first rule is related to the priorities. The second
rule is that, if scanned operator is less than
or equal to than the top of the second
priority, then pop operators until we have
low priority, add the popped elements to the postfix.
Next, if we have the opening
parenthesis, then we will just push it into
the stack and if we have a closing
parenthesis, then we will pop elements from
the stack until we reach the opening parenthesis.
And all the popped elements will be
added to the postfix. Finally if we have
operand, we will just add it to the postfix expression.
If we look at the rules from 2 to 5,
there will be checks for each symbol
that is being processed. At any point, at any
time one of these rules will be applicable.
This means that we can use a match statement
for implementing this. Let us define a
function for implementing the conversion to
postfix, I will use the name of infix_to_postfix for this function.
The input to this function will be
a vector of strings, containing the symbols.
[No Audio]
The output of this function will be a vector
of strings, containing the symbols in postfix notation.
[No Audio]
Inside the function, I will first
declare a variable for storing the size of
the input vector of strings, and we'll name it
as size_expr.
[No Audio]
We need the size information to make an appropriate
size stack, which will be used in our
processing of conversion to postfix.
Next, I will make the stack using the new_stack function.
[No Audio]
To store the final postfix
expression, I will declare a vector of strings called postfix.
[No Audio]
Okay we are done with the
variables. Now, next, I am going to iterate
through all the symbols in the input using a for loop.
[No Audio]
Let us get rid of the red lines by returning
postfix outside the for loop, as it is a bit distracting.
[No Audio]
The red line kinds of creates
some distraction, and it is always a good idea
to get rid of them as soon as possible. You
may note, that the type of the variable i is
that of a string and not a string reference,
which means that the variable I assumed
the ownership of the values.
Next, we will do a match on the current symbol, which
is given by the variable i.
[No Audio]
We will put some conditions to check, if rule 2
can be applied or not. Let us see the
rule 2 again. The starting lines of this
rule says that, if operator is less than or
equal to in priority, let us stop reading
here the rule. This means that, this rule is
applicable in case of operator. So let us
have an arm for checking if the
symbol is an operator or not.
[No Audio]
You might note, that the compiler result is complaining about
the types, anything inside the double quotes
is treated as a string reference type and not
a string type. So let us convert the variable
i to that of a string slice type, which can
be done using the as_str function.
Also note that the as_str
does not take ownership as it uses a reference.
We will not write the complete logic inside
this arm right now, we will first complete
the different arms that we may expect
corresponding to different rules, and then we
will add code to each of these ones.
This will help us having a holistic view first.
Let us now add another arm corresponding to
rule 3,4 and 5. The rule 3 and
4 checks for the opening and closing
parenthesis respectively. So I will add an
arm corresponding, to rule 3 first, and
then for rule 4.
[No Audio]
Finally if none of the arms are valid, then
we will have a default default arm which will
correspond to rule 5, and which will mean
that the symbol corresponds to an operand.
[No Audio]
Okay, now the skeletal of our code is more or
less complete. Let us add code to the
individual blocks now one by one.
We will start with the first one which corresponds
to rule 2. To apply rule 2, we will need to
first determine the priority of the operands.
I will define another function
for determining the priority of an operand.
I will name this function as priority, the
input to this function will be a string
reference containing the operator, and the
output will be an unsigned number indicating
the priority corresponding to the input operator.
[No Audio]
Inside the function, we will check
the operator and then assign appropriate
priorities accordingly. I will use the if
else, if structure here to code this part. Of
course, we can also use the match statement
in this case also. First, we will check for
the operator being addition or subtraction,
and we'll set its priority to the minimum value.
[No Audio]
Next, we will set the priorities for
the multiplication and division.
[No Audio]
Finally we will set the priority for the exponent.
[No Audio]
Finally, I will include an else part, where I
will set the priority to that of 0. We need
it because, if you recall the example, there
was a case when we were matching the top of the
stack with that of the opening parenthesis.
And in that case, we mentioned that the
opening parenthesis are considered to have
least priority, compared to any of the
operators. So, to take all that, we will
use this else part, which will corresponds to
an opening parenthesis. Okay, now let us come
back again to the first arm.
[No Audio]
I will first check if the priority of the scanned operator is
greater than the top of the stack, then we
will just push the operator onto the stack.
The priority function will be used to return
the priority in this case, moreover the top
of the stack is given by the last function.
If this condition is true, then we will use
the push function to add the element to the stack.
[No Audio]
Please note that, the last function
when called on the stack, will return a
reference, and therefore the compiler is not
complaining with regards to the input to the
priority function, which accepts a string
reference. When this condition is not true,
which will mean that the top of the stack is
lesser than or equal to in priority, then the
scanned symbol. So in this case, we will pop
elements from the stack until the top of the
stack becomes lesser in priority than the
scanned symbol or the current operator.
To implement this, I will use a while loop,
which will iterate until the priority of the
scanned symbol become lesser to or equal to in
priority than the top of the stack.
[No Audio]
Inside the loop, we will pop the elements from
the stack, and we'll add it to the postfix
expression. These two operations are done
using a single statement.
[No Audio]
Now sometimes it may happen that, while
popping the elements from the stack, we may
reach to the end of the stack, and checking
more elements may therefore leads to an error.
To avoid that, we will write one
additional check before executing the
next iteration of the loop. This will check if
there exists the top element or not.
[No Audio]
If this becomes true, so we will break out from the while loop.
[No Audio]
In this case, the meaning will be
that all the elements in the stack are
greater than or equal to priority than the
current operator.
When the loop ends, we are
sure that the current element
has now greater priority, so it is
safe to push it to the stack.
So let us push it.
Okay, we are almost done with
this arm. But wait, what will happen to the
code when we encounter the first operator?
In this case our stack will be empty. I
will give you 10 seconds to think, and then I
will tell you the answer.
[No Audio]
I believe you would have guessed the answer.
In this case, the if statement will give an
error, because the function stack.last
will return a None value, and we cannot unwrap
an null value. Since this is the first operator
and the stack is empty, we may just add it to
the stack, because the top of the stack is empty.
This means that, we will always add an
operator to the stack if the stack is empty.
To avoid this error, I will include a simple
if statement, which will check the size, and if
the size is 0, then we will push the
operator onto the stack.
[No Audio]
All the remaining code will go to the else part.
[No Audio]
Now this arm is complete, for the next arm, the code is very
simple. When we encountered the opening
parenthesis so the rule 3 says,
that we just need to push it onto the stack.
So let me add a suitable statement.
[No Audio]
Since there is only a single statement inside
this arm, so we do not require the curly brackets.
However for the correct syntax,
we are required to write a comma at the end
of the statement. The next arm corresponds to
the closing parenthesis. In this case, we
will pop up elements until we encountered the
opening parenthesis, all the popped elements will
be added to the postfix expression. I will do
this using a while loop. The while
loop will iterate as long as we do
not encounter the opening parenthesis.
[No Audio]
Inside the loop, I will add the popped elements to the postfix.
[No Audio]
Finally, we will also remove the opening
parenthesis by popping it from the stack.
[No Audio]
This will remove the opening parenthesis from
the stack. Let us now code the default arm.
When none of the arms above is true, then the
default arm will be executed, which is an
indication that the current symbol is an
operand. This means that we are now in rule 5,
and rule 5 says that, we just need to
add the operand to the postfix.
So let us use it.
[No Audio]
Again, as there as a single statement, so we
will remove the brackets and we'll add a comma.
As pointed out in the example, when all
the symbols are scanned, and if there is
something left in the stack, so we will
just pop it until the stack becomes empty,
and we'll add all the elements to the postfix.
We will use a while loop again, which will
iterate until the size of the stack becomes empty.
[No Audio]
Inside the body of the while loop, we will pop
elements from the stack, and we'll add them to
the postfix.
[No Audio]
Okay done, finally, I will print
the resulting expression.
[No Audio]
Now let us move to
the main function, and call this function, and
we'll store the result in postfix variable.
[No Audio]
Let us cargo run this to see the final
postfix expression.
[No Audio]
We have the original expression and the
resultant postfix expression, that is great.
This brings us to the end of this tutorial, we
have implemented how to convert the infix or
original expression to the postfix
expression. While doing so, we have practiced
majority of the concepts that we have learned so far.
Please note that this implementation,
may not be the most optimal one, but the
objective here is not to have an optimal
implementation, but rather practice the
concepts that we have learned so far. Once we
have sufficient skills and programming, we
can always review our code and make the
optimization in code. In the next tutorial, we
will be implementing the last part, and that
will be the computation of the final result
from the postfix expression. Do come back
again for covering that, and until then happy
Rust programming.
[No Audio]