Tip:
Highlight text to annotate it
X
In our previous lesson, we saw how we can evaluate prefix and postfix expressions,
now in this lesson we will see an efficient algorithm to convert infix to postfix. We
already know of one way of doing this. We have seen how we can do this manually. To
convert an infix expression to postfix, we apply operator precedence, and associativity
rules. Let's do the conversion for this expression we have written here. The precedence of multiplication
operator is higher. So, we will first convert this part B*C. B*C will become BC*. The operator
will come in front of the operands. Now, we can do the conversion for this addition. For
addition, the operands are A and this postfix expression. In the final step we can get rid
of all the parentheses. So, finally this is my post fix expression.
We can use this logic in a program also. But, it will not be very efficient. And the implementation
will also be somewhat complex. I am going to talk about one algorithm which is really
simple and efficient and in this algorithm we need to parse the infix expression only
once from left to right. And, we can create the postfix expression. If you can see in
infix to postfix conversion, the positions of operands and operators, may change but
the order in which operands occur from left to right will not change. The order of operators
may change. This is an important observation. In both infix and postfix forms here, the
order of operands as we go from left to right is first we have A, then we have B and then
we have C. But, the order of operators is different. In infix, first we have + and then
we have multiplication. In postfix, first we have multiplication and then we have addition.
In postfix form we will always have the operators in the same order, in which they should be
executed. I am going to perform this conversion once again but this time I am going to use
a different logic. What I will do is, I will parse the infix expression from left to right.
So, I will go from left to right, looking at each token that will either be an operand
or an operator. In this expression we will start at A, A is an operand. If it's an operand
we can simply append it in the postfix string or expression that we are trying to create.
At least for A it should be very clear that this is nothing that can come before A. Okay,
so the first rule is that if it's in operand, we can simply put it in the postfix expression.
Moving on, next we have an operator. We cannot put the operator in the postfix expression,
because we have not seen it's right operand yet. While parsing we have seen only it's
left operand. We can place it only after it's right operand is also placed. So, what I am
going to do is I am going to keep this operator in a separate list or collection and place
it later in the postfix expression when it can be placed and the structure that I am
going to use for storage is stack. A stack is only a special kind of list in which whatever
comes in last goes out first. Insertion and deletion happen from the same end. I have
pushed + operator onto the stack here. Moving on, next we have B which is an operand. As
we had said operand can simply be appended. There is nothing that can come before this
operand. The operator on the stack is anyway waiting for the operand to come. Now at this
stage, can we place the addition operator, to the postfix string. Actually, what's after
B also matters. In this case, we have this multiplication operator after B, which has
higher precedence and so the actual operand for addition is this whole expression B*C.
We cannot perform the addition until multiplication is finished. So while parsing, when I am at
B and I have not seen what's ahead of B, I cannot decide the fate of the operator in
the stack. So, let's just move on. Now, we have this multiplication operator. I want
to make this expression further complex to explain things better. So, I am adding something
at tail here in this expression. Now, I want to convert this expression to postfix form.
I am not having any parentheses here. We will see how we can deal with parentheses later,
let's look at an expression where parentheses does not override operator precedence. Okay,
so right now in this expression while parsing from left to right, we are at this multiplication
operator. The multiplication operator itself cannot go into the postfix expression because
we have not seen it's right operand yet. And, until it's right operand is placed in the
postfix expression, we cannot place it. The operator that we would be looking at while
parsing. That operator itself cannot be placed right away. But, looking at that operator,
we can decide whether something from the collection, something from the stack can be placed into
the postfix expression that we are constructing or not. Any operator in the stack having higher
precedence than the operator that we are looking at, can be popped and placed into the postfix
expression. Let's just follow this as rule for now and I will explain it later. There
is only one operator in the stack and It is not having higher precedence than multiplication
so we will not pop it and place it in the postfix expression. Multiplication itself,
will be pushed. If an element in the stack has something on top of it, that something
will always be of higher precedence. So, let's move on in this expression now. Now, we are
at C, which is an operand, so, it can simply go. Next, we have an operator subtraction.
Subtraction itself cannot go but as we had said if there is anything on the stack having
higher precedence than the operator that we are looking at, it should be popped out and
it should go and the question is why? We are putting these operators on the stack, we are
not placing them on the postfix expression because we are not sure whether we are done
with their right operand or not. But after that operator, as soon as I am getting an
operator of lower precedence, that marks the boundary of the right operand. For this multiplication
operator, C is my right operand. It's this simple variable. For addition, B*C is my right
operand because subtraction has lower precedence. Anything on or after that cannot be part of
my right operand. Subtraction, I should say has lower priority because of the associativity
rule. If you remember the order of operation, addition and subtraction have same precedence
but the one that would occur in left would be given preference. So, the idea is anytime
for an operator, if I am getting an operator of lower priority, we can pop it from the
stack and place it in the expression. Here, we will first pop multiplication and place
it and then we can pop addition and now we will push subtraction onto the stack. Let's
move on now. D is an operand. So, it will simply go. Next we have, multiplication. There
is nothing in the stack having higher precedence than multiplication. So, we will pop nothing.
Multiplication will go on to the stack. Next, we have an operand. It will simply go. Now,
there are two ways in which we can find the end of the right operand for an operator.
a is if we get an operator of lesser precedence, b if we reach the end of the expression. Now,
that we have reached end of the expression, we can simply pop and place these operators.
So, first multiplication will go and then subtraction will go. Let's quickly write pseudo
code for whatever I have said so far and then you can sit with some examples and analyse
the logic. I am going to write a function named infix to postfix that will take a string
exp for expression as argument. For the sake of simplicity, lets assume that each operand
or operator will be of one character only. In an actual implementation you can assume
them to be tokens of multiple characters. So, in my pseudo code here, the first thing
I will do is, to create a stack of characters named S. Now, I will run a loop starting 0
till length of expression -1. So, I am looking at each character that can either be an operand
or operator. If the character is an operand we can append it to the postfix expression.
Well, actually I should have declared and initialized a string before this loop. This
is the result string in which I shall be appending else if exp[i] is operator, we need to look
for operators in the stack having higher precedence. So, I will say while stack is not empty, and
top of stack has higher precedence. And let's say this function HasHigherPrecedence will
take two arguments, two operators. So, if the top of Stack has higher precedence than
the operator that we are looking at. We can append the top of stack to the result which
is the variable that will store the postfix string. And, then we can pop that operator.
I am assuming that this S is some class that has these functions top and pop and empty
to check whether it's empty or not. Finally, once I am done with the popping, Outside this
while loop I need to push the current operator. S is an object of some class that will have
these functions top, pop and empty. Okay, so this is the end of my for loop. At the
end of it, I may have some operators left in the stack. I will pop these operators and
append them to the postfix string. I will use this while loop. I will say that while
the stack is not empty, append the operator at top and pop it. And, finally after this
while loop I can return the result string that will contain the postfix expression.
So, this is my pseudo code for whatever logic I have explained so far. In the logic, I have
not taken care of parentheses. What if my infix expression would have parentheses like
this? Their will be slight change from what we were doing previously. With, parentheses
any part of the expression within parentheses should be treated as independent complete
expression in itself. And, no element outside the parentheses will influence its execution.
In this expression, this part A + B is within one parentheses. It's execution will not be
influenced by this multiplication or this subtraction which is outside it. Similarly,
this whole thing is within the outer parentheses. So, this multiplication operator outside,
will not have any influence on execution of this part as a whole. If parentheses are nested,
inner parentheses is sorted out or resolved first,and then only outer parentheses can
be resolved. With parentheses, we will have some extra rules: we will still go from left
to right and we will still use stack. And, let's say I am going to write the postfix
part in write here as I create it. Now, while parsing, a token can be an operand or operator
or an opening or closing of parentheses. I will use some extra rules. I will first tell
them and then I will explain. If it's an opening parentheses, we can push it onto the stack.
The first token here, is an opening parentheses. So, it will be pushed onto the stack. And,
then we will move on. We have an opening parentheses once again, so once again we will push it.
Now, we have an operand. There is no change in rule for operand. It will simply be appended
to the postfix part. Next, we have an operator. Remember, what we were doing for operator
earlier. We were looking at top of stack and popping as long as we were getting operator
of higher precedence. Earlier when we were not using parentheses, we could go on popping
and empty the stack. But, now we need to look at top of stack and pop only till we get an
opening parentheses. Because, if we are getting an opening parentheses, then it's the boundary
of the last opened parentheses and this operator does not have any influence after that, outside
that. So, this + operator does not have any influence outside this opening parentheses.
I will explain this scenario, with some more examples later. Let's first understand the
rules. So, the rule is, if I am seeing an operator, I need to look at the top of stack.
If it's an operator of higher precedence, I can pop and then I should look at the next
top. If it's once again an operator of higher precedence, I should pop again. But, I should
stop when I see an opening parentheses. At, this stage we have an opening parentheses
at top, so we do not need to look below it. Nothing will be popped anyway. Addition however,
will go on to the stack. Remember, after the whole popping game, we push the operator itself.
Next, we have an operand. It will go on, we will move on. Next, we have a closing of parentheses.
When I am getting a closing of parentheses, I am getting a logical end of the last opened
parentheses. For part of the expression, within that parentheses, it's coming to the end.
And, remember what we were doing earlier, when we were reaching the end of infix expression,
we were popping all the operators out and placing them. So, this time also we need to
pop the operators out, but only those operators that are part of this parentheses that we
are closing. So, we need to pop all the operators until we get an opening parentheses. I am
popping this + and appending it. Next, we have an opening of parentheses, so I will
stop. But, as last step I will pop this opening also. Because, we are done for this parentheses.
Okay, so the rule for closing a parentheses, is pop until you are getting an opening parentheses
and then finally pop that particular opening parentheses also. Let's move on now. Next,
we have an operator. We need to look at top of stack. It's an opening of parentheses.
This operator will simply be pushed. Next, we have an operand. Next, we have an operator.
Once again, we will look at the top. We have multiplication, which is of higher precedence.
So, this should be popped and appended. We will look at the top again. Again, it's an
opening of parentheses, so we should stop looking now. '-' will be pushed now. Next,
we have an operand. Next we have a closing of parentheses. So, we need to pop until we
get an opening. '-' will be appended. Finally, the opening will also be popped. Next, we
have an operator and this will simply go. Next, we have an operand. And, now we have
reached the end of expression. So, everything in the stack will be popped and appended.
So, this final is my postfix expression. I will take one more example and convert it
to make things further clear. I want to convert this expression. I will start at the beginning.
First, we have an operand. Then this multiplication operator, which will simply go onto the stack.
The stack right now, is empty. There is nothing on the top to compare it with. Next, we have
an opening parentheses which will simply go. Next, we have an operand it will be appended
and now we move on to this addition operator. If this opening parentheses was not there,
the top of stack would have been the multiplication operator which has higher precedence. So,
it would have been popped. But, now we will look at the top and it's an opening parentheses.
So, we cannot look below. And we will simply have to move on. Next, we have C. I missed
pushing the addition operator last time. Okay, after C, I have this closure. So, we need
to pop until we get an opening. And, then we need to pop one opening also. Finally we
have reached the end of expression. So, everything in the stack will be popped and appended.
So, this finally is my postfix part, postfix form. In my pseudo code, that I had written
earlier, only the part within this for loop will change to take care of parentheses. In
case we have an operator, we need to look at top of the stack and pop but only till
we are an getting opening parentheses. So, I have put this extra condition in the while
loop, this condition will ensure that we stop once we get an opening parentheses. Right
now, in the for loop we are dealing with operand and operators, we will have two more conditions:
If its an opening of parentheses, we should push. Else, if it's a closure, we can go on
popping and appending. Let's say this function IsOpeningParentheses will check whether a
character is opening of parentheses or not. In fact we should use this function here also
when I am checking whether current token is opening or not. Because, it could be an opening
curly brace or opening bracket also, this function will then take care. Let's say this
function will take care. And, similarly for this last else if, we should use this function
IsClosingParentheses. Okay, things are consistent now. After this while loop in the last else
if, we should do one extra pop. And, this extra pop will pop the opening parentheses.
And, now we are done with this else if. And, this is closure of my for loop. Rest of the
stuff will remain same. After the for loop, we can pop the left overs and append to the
string. And, finally we can return. So, this is my final pseudo code. You can check the
description of this video for a link to the real implementation, actual source code. Okay,
So, I will stop here now. This is it for this lesson. Thanks, for watching.