[No Audio]
Welcome back again. I know you have been
waiting for some time now to start
implementing the Expression Evaluation using stack.
So, let's dive into it straightaway.
I am starting with the same code, that we
used and saw, where we were implementing
the stacks with the slight change, which I
will explain in a second. And this
implementation, we assume that the expression
we will be given is in the form of a string.
So, this means there is the individual symbol
expressions that is operands and operators
will be in string format. So, therefore, to
save some time, I have already changed all
the definitions of all the functions of the
stack based on strings. The rest of the code
is more or less the same as that of the code
covered in the first lecture when we were
implementing the stack. Let us now start with
some code in the main function.
I will declare a variable called input_expr
or expr, which contains
the expression that we used in the examples.
[No Audio]
I will print this expression also
[No Audio]
the individual symbols in this string, and
by symbols, I mean operands to be specific, may
contain any number of characters. We cannot
perform operations on the characters in this
case, because the number may occupy more
than one character. For instance, if we have
a number consisting of three digits in the
expression, then it will consume three
characters, and if it is a number such as
1043, then it will consume four characters and so on.
We therefore needs to have a
function, which will return to us the
individual symbols inside the expressions.
I will declare a function for this purpose
called individual symbols.
[No Audio]
This function will convert the given expression into the
individual symbols, and will return the
individual symbols as elements of a string vector.
The input to this function will be a
string, and the output will be a vector of strings.
[No Audio]
Inside the function, I will first declare a
mutable variable which will be used for
storing the final result in the form of
individual symbols. I will call it tokenized_input.
Since the final symbols
will be contained in a vector of strings, so
therefore, I will mention its types to be
that of string back, and we'll initialize it
as an empty string. Next I'm going to
iterate through all the characters of the
input_expr one by one,
therefore, I will need to convert the given
string into vector of characters.
The char function will be used for this purpose, and
the result will be collected in a variable
of input_char. The collect
function converts the result to any
collection type, such as vector of strings in this case.
We will cover the same function in
the later on sections of the course under the
topic of Hydrators.
For now, just note that
it can be used to turn one collection into another.
Next, I will use a for loop for
iterating through each character in the
input_char vector one by one.
[No Audio]
Inside the loop, I will first check if the
character is an operand or operator. I will
check if the character is not equal to one of
the operator, that is, plus, minus, that is
multiplication, divides and exponent.
In case it is an operator, so I will add to the
vector of strings, and in case it is not, then
I will keep on iterating, until I find out the next operator.
Let me add the code to check, if
the input_char is an operator or not.
[No Audio]
In addition to operators, I will also check
and add conditions, if it is an opening or
closing parenthesis.
[No Audio]
Now let us move to the
else part, which will mean that, none of the
above conditions are being true, and
therefore, the character does not corresponds
to AND operator and neither it is
opening or closing parenthesis. Since the
operand can be of any length, as explained a
little while ago, that is, it can consist of
any number of digits, so therefore, I will
keep on pushing this to a temp vector
until I found a AND operator or parentheses.
So outside the body of the loop,
I will define a vector of chars called temp,
and we'll initialize it as an empty vector.
[No Audio]
Inside the if statement, I will use it to
store the character by pushing them into it.
[No Audio]
I will now grade the next character. And to do
that, I will skip everything that is coming
afterwards in the same loop, which can be
done with the help of continue statement.
This means now, that the temp will contain
operands only. In summary, as long as the if
part remains true, the temp will keep on
accumulating all the characters or digit
of a certain operand. Now let us code the else part.
In the else part, I will first change
the variable temp, which contains the
individual characters in an operand, to that of
a string, and then I will push it on to the
tokenized_input. I will use the
collect function which will collect all the
individual characters in the variable temp as a string.
And we'll add it as a single string
element into the vector of tokenized_input.
[No Audio]
Next, I will also push the current character
which is given by the variable i into the
tokenized_input which corresponds
to an operation.
[No Audio]
At the end, I will flush
everything from the temp vector, because I am
now expecting another operand, as the current
operand has ended. This means that each time
I encounter an operation, I will flush out
the temp, since I am expecting another operand now.
[No Audio]
Okay outside the body of the loop, I
will return the tokenized_input by
writing tokenized_input.
I will also add a print statement for displaying the
tokenized_input.
[No Audio]
Let us call this function from the main now.
I will store its result in a suitable variable.
[No Audio]
This program contains an error from
computational perspective, which will
become evident now, let us cargo run this.
[No Audio]
You may note, that it has converted the given
expression correctly into individual tokens
or strings contained in a string vector.
The individual symbols are indicated by
characters enclosed in double quotes.
You may have spotted that the first symbol is
empty, that is, there is nothing inside the
double quotes which should have not happened.
Let us see why this happened.
[No Audio]
For the first time when the loop starts, we have the symbol
of opening parenthesis. So therefore, the
else part will be executed, which means that,
there is nothing in the temp and is empty.
So pushing it onto the tokenized_input
will lead to an empty string, and empty
entry into the vector. To make this not to
happen, we will add an if condition inside
the else part, where we will check if the
length of the temporary string variable is
empty or not.
[No Audio]
We will just add the operator
in this case, as there is no operand in this case to add.
[No Audio]
This will happen when we are
processing the first symbol in the expression..
And in the else part, we will do the
processing as usual, so all the remaining
statements will be added to the else part.
Let me execute again.
[No Audio]
You may note that, this is working fine now.
The expression that we were currently,
considering, was ending at a closing parenthesis.
Sometimes we may have
expressions which may end in an operand, in
this case the code will fail. For instance,
let me change the input expression in the
main function.
[No Audio]
Let us execute again now.
[No Audio]
You may note that, the symbols are being
identified correctly, which are enclosed in
double quotes. However, the last symbol has
not been identified correctly, which has a
value of 36. Let us see why this happened. I
will copy the same expression, and we'll paste
it as a comment, just before the start of the loop.
[No Audio]
Since there is an error in the
last operand identification, so let us focus
on what will happen inside the loop when we
reach at the final operation. When the final
operation is reached, which is a minus, so
anything which has been found as operand,
will be pushed onto the stack using the else part.
The loop will then continue with the
remaining characters, that is 3 and 6,
and we'll push it on to the attempt variable.
Now we never push them into the tokenized_input,
so therefore they are
not part of the tokenized_input.
This means that our loop assumed that, we will
always encounter an operand or closing or
parenthesis at the end, which is
not the case in this expression. To counter
this, I will add one more if statement
outside the body of the for loop. If there is
something left, so I will push it on to the
tokenized_input. This will ensure
that if there is anything left in the temp,
we will push it on to the tokenized_input.
Let me execute once more.
[No Audio]
You may note that, yes, we have the last symbol
also being detected successfully. To make
the code look a bit better, I will run the
command of cargo fmt, which will nicely
format the code for us.
[No Audio]
The fmt is a nice and handy utility for
formatting our code. Now that our code has
been converted into individual symbols or
tokens, we are now ready to implement the
conversion to postfix and then expression
evaluation from the postfix. We will cover
that in the remaining of the
implementation in the next tutorial.
Do come back again, as the interesting part is yet to begin.
Until next tutorial, happy Rust programming.
[No Audio]