Infix to Postfix Conversion

In order to convert infix to postfix expression, we need to understand the precedence of operators first.

Precedence of Operators

There are five binary operators, called addition, subtraction, multiplication, division and exponentiation. We are aware of some other binary operators. For example, all relational operators are binary ones. There are some unary operators as well. These require only one operand e.g. – and +. There are rules or order of execution of operators in Mathematics called precedence. Firstly, the exponentiation operation is executed, followed by multiplication/division and at the end addition/subtraction is done. The order of precedence is 

(highest to lowest):

Exponentiation ­

Multiplication/division *, /

Addition/subtraction +, -

For operators of same precedence, the left-to-right rule applies:
A+B+C means (A+B)+C.

For exponentiation, the right-to-left rule applies:
A ­ B ­ C means A ­ (B ­ C)

We want to understand these precedence of operators and infix and postfix forms of expressions. A programmer can solve a problem where the program will be aware of the precedence rules and convert the expression from infix to postfix based on the precedence rules.

 

Examples of Infix to Postfix

Let’s consider few examples to elaborate the infix and postfix forms of expressions based on their precedence order:

Infix	Postfix
A + B 12 + 60 – 23 (A + B)*(C – D ) A ­ B * C – D + E/F	A B + 12 60 + 23 – A B + C D – * A B ­ C*D – E F/+

A programmer can write the operators either after the operands i.e. postfix notation or before the operands i.e. prefix notation. Some of the examples are as under:

Infix	Postfix
A + B	A B +
12 + 60 – 23	12 60 + 23 –
(A + B)*(C – D )	A B + C D – *
A ­ B * C – D + E/F	A B ­ C*D – E F/+

The last expression seems a bit confusing but may prove simple by following the rules in letter and spirit. In the postfix form, parentheses are not used. Consider the infix expressions as ‘4+3*5’ and ‘(4+3)*5’. The parentheses are not needed in the first but are necessary in the second expression. The postfix forms are:

4+3*5 435*+
(4+3)*5 43+5*

In case of not using the parenthesis in the infix form, you have to see the precedence rule before evaluating the expression. In the above example, if we want to add first then we have to use the parenthesis. In the postfix form, we do not need to use parenthesis. The position of operators and operands in the expression makes it clear in which order we have to do the multiplication and addition.

Now we will see how the infix expression can be evaluated. Suppose we have a postfix expression. How can we evaluate it? Each operator in a postfix expression refers to the previous two operands. As the operators are binary (we are not talking about unary operators here), so two operands are needed for each operator. The nature of these operators is not affected in the postfix form i.e. the plus operator (+) will apply on two operands. Each time we read an operand, we will push it on the stack. We are going to evaluate the postfix expression with the help of stack. After reaching an operator, we pop the two operands from the top of the stack, apply the operator and push the result back on the stack. Now we will see an example to comprehend the working of stack for the evaluation of the postfix form. Here is the algorithm in pseudo code form. After reading this code, you will understand the algorithm.

Stack s; // declare a stack while( not end of input ) { // not end of postfix expression e = get next element of input if( e is an operand ) s.push( e ); else { op2 = s.pop(); op1 = s.pop(); value = result of applying operator ‘e’ to op1 and op2; s.push( value ); } } finalresult = s.pop();

We have declared a Stack‘s’. There is a ‘while loop’ along with ‘not end of input’ condition. Here the input is our postfix expression. You can get the expression from the keyboard and use the enter key to finish the expression. In the next statement, we get the next element and store it in ‘e’. This element can be operator or operand. The operand needs not to be single digit. It may be of two digits or even more like 60 or 234 etc. The complete number is stored in the ‘e’. Then we have an ‘if statement’ to check whether ‘e’ is an operand or not. If ‘e’ is an operand than we wrote s.push(e) i.e. we pushed the ‘e’ onto the stack. If ‘e’ is not the operand, it may be an operator. Therefore we will pop the two elements and apply that operator. We pop the stack and store the operand in ‘op2’. We pop the stack again and store the element in ‘op1’. Then the operator in ‘e’ is applied to ‘op1’ and ‘op2’ before storing the result in value. In the end, we push the ‘value’ on the stack. After exiting the loop, a programmer may have only one element in the stack. We pop this element which is the final result.

Consider the example of 4+3*2 having a postfix form of 432*+. Here 4, 3, and 2 are operands whereas + and * are operators. We will push the numbers 4, 3 and 2 on the stack before getting the operator *. Two operands will be popped from the stack and * is being applied on these. As stack is a LIFO structure, so we get 2 first and then 3 as a result of pop. So 2 is store in ‘op1’ and 3 in ‘op2’. Let’s have a look on the program again. On applying * on these, we will push the result (i.e. 6) on the stack. The ‘while loop’ will be executed again. In case of getting the next input as operand, we will push it on the stack otherwise we will pop the two operands and apply the operator on these. Here the next element is the operator +. So two operands will be popped from the stack i.e. 6 and 4. We will apply the operator plus on these and push the result (i.e. 10) on the stack. The input is finished. Now we will pop the stack to get the final result i.e. 10.

 Postfix Expression solved by Example

In the earlier example, we have used the stack to solve the postfix expression. Let’s see another comprehensive example. The postfix expression is:

6 2 3 + - 3 8 2 / + * 2 ­ 3 +

We want to evaluate this long expression using stack. Let’s try to solve it on paper. We have five columns here i.e. input, op1, op2, value and stack. We will run our pseudo code program. In the start, we read the input as a result we get number 6. As 6 is operand, so it will be pushed on the stack. Then we have number 2 which will also be pushed on the stack. Now 2 is the most recent element. The next element is the number 3 that will also be pushed on the stack. Now, there are three elements on the stack i.e. 3, 2 and 6. The number 3 is the most recent. On popping, we will get the number 3 first of all. The next element is ‘+’, an operator. Now the else part of our pseudo code is executed. We will pop two operands from the stack and apply the operator (+) on these. The number 3 will be stored in variable op2 and number 2 in op1. The operator (+) will be applied on these i.e. 2+3 and the result is stored in value. Now we will push the value (i.e. 5) on the stack. Now we have two numbers on the stack i.e. 5 and 6. The number 5 is the most recent element. The next element is ‘-‘. As it is also an operator, so we will pop the two elements from the stack i.e. 5 and 6. Now we have 5 in op2 and 6 in op1. On applying the operator (-), we will get the result as 1 (6-5). We can’t say op2 - op1. The result (1) will be pushed on stack. Now on the stack, we have only one element i.e. 1. Next three elements are operands so we pushed 3, 8 and 2 on the stack. The most recent element is 2. The next input is an operator in the expression i.e. ‘/’, we will pop two elements from the stack. The number 2 will be stored in op2 while number 8 in op1. We apply the operator (/) on the op1 and op2 i.e. (op1/op2), the result is 4 (i.e. 8/2). We push the result on the stack. We have, now, three elements i.e. 4, 3, and 1 on the stack. The next element is operator plus (+). We will pop the two elements i.e. 4 and 3 and will apply the operator (+). The result (7) will be pushed on the stack. The next input element is operator multiply (*). We will pop the two elements i.e. 7 and 1 and the result (7*1 = 7) is pushed on the stack. You have noted that whenever we have an operator in the input expression, we have two or more elements on the stack. As the operators we are using are binary and we need two operands for them. It will never be the case that you want to pop two elements from the stack and there is only one or no element on the stack. If this happens than it means there is an error in the program and you have popped more values than required. The next input element is 2 that is pushed on the stack. We have, now, the operator ( ­ ) in the input. So we will pop the two elements, op2 will hold 2 and op1 will have the number 7. The operator ( ­ ) will be applied on the operands i.e. (7 ­ 2) and the result (49) is pushed on the stack. We have, now, the number 3 in the element being pushed on the stack. The last element is the operator plus (+). So we pop the two elements i.e. 49 and 2 and apply the operator on these. The result (49+3 = 52) is pushed on the stack. The input expression is finished, resulting in the final result i.e. 52.

This the tabular form of the evaluation of the postfix expression.

Input	op1	op2	value	stack
6				6
2				2 6
3				3 2 6
+	2	3	5	5 6
-	6	5	1	1
3	6	5	1	3 1
8	6	5	1	8 3 1
2	6	5	1	2 8 3 1
/	8	2	4	4 3 1
+	3	4	7	7 1
*	1	7	7	7
2	1	7	7	2 7
­	7	2	49	49
3	7	2	49	3 49
+	49	3	52	52

With the help of stack we can easily solve a very big postfix expression. Suppose you want to make a calculator that is a part of some application e.g. some spreadsheet program. This calculator will be used to evaluate expressions. You may want to calculate the value of a cell after evaluating different cells. Evaluation of the infix form programmatically is difficult but it can be done. We will see another data structure which being used to solve the expressions in infix form. Currently, we have to evaluate the values in different cells and put this value in another cell. How can we do that? We will make the postfix form of the expression associated with that cell. Then we can apply the above algorithm to solve the postfix expression and the final result will be placed at that cell. This is one of the usages of the stack.

Infix to postfix Conversion

We have seen how to evaluate the postfix expressions while using the stack. How can we convert the infix expression into postfix form? Consider the example of a spreadsheet. We have to evaluate expressions. The users of this spreadsheet will employ the infix form of expressions. Consider the infix expressions ‘A+B*C’ and ‘(A+B)*C’. The postfix versions are ‘ABC*+’ and ‘AB+C*’ respectively. The order of operands in postfix is the same as that in the infix. In both the infix expressions, we have the order of operands as A, B and then C. In the postfix expressions too, the order is the same i.e. A, B, followed by C. The order of operands is not changed in postfix form. However, the order of operators may be changed. In the first expression ‘A+B*C’, the postfix expression is ‘ABC*+’. In the postfix form multiplication comes before the plus operator. In scanning from left to right, the operand ‘A’ can be inserted into postfix expression. First rule of algorithm is that if we find the operand in the infix form, put it in the postfix form. The rules for operators are different. The ‘+’ cannot be inserted in the postfix expression until its second operand has been scanned and inserted. Keep the expression A+B*C in your mind. What is the second operand of the plus? The first operand is A and the second operand is the result of B*C. The ‘+’ has to wait until the ‘*’ has not been performed. You do the same thing while using the calculator. First you will multiply the B*C and then add A into the result. The ‘+’ has to be stored away until its proper position is found. When ‘B’ is seen, it is immediately inserted into the postfix expression. As ‘B’ is the operand, we will send the operand to the postfix form. Can the ‘+’ be inserted now? In case of ‘A+B*C’, we cannot insert ‘+’ because ‘*’ has precedence. To perform multiplication, we need the second operand. The first operand of multiplication is ‘B’ while the second one is ‘C’. So at first, we will perform the multiplication before adding result to ‘A’.

In case of ‘(A+B)*C’, the closing parenthesis indicates that ‘+’ must be performed first. After sending the A and B to postfix perform, we can perform the addition due to the presence of the parenthesis. Then C will be sent to the postfix expression. It will be followed by the multiplication of the C and the result of A + B. The postfix form of this expression is AB+C*. Sometimes, we have two operators and need to decide which to apply first like in this case ‘+’ and ‘*’. In this case, we have to see which operator has higher precedence. Assume that we have a function ‘prcd(op1,op2)’ where op1 and op2 are two operators. The function ‘prcd(op1,op2)’ will return TRUE if op1 has precedence over op2, FASLE otherwise. Suppose we call this function with the arguments ‘*’ and ‘+’ i.e. prcd(*, +), it will return true. It will also return true in case both op1 and op2 are ‘+’ e.g. if we have A+B+C, then it does not matter which + we perform first. The call prcd(+ , *) will return false as the precedence of * is higher than the + operator. The ‘+’ has to wait until * is performed.

Now we will try to form an algorithm to convert infix form into postfix form. For this purpose, a pseudo code will be written. We will also write the loops and if conditions. The pseudo code is independent of languages. We will be using a stack in this algorithm. Here, the infix expression is in the form of a string. The algorithm is as follows:

Stack s;

while( not end of input ) {

c = next input character;

if( c is an operand )

add c to postfix string;

else {

while( !s.empty() && prcd(s.top(),c) ){

op = s.pop();

add op to the postfix string;

}

s.push( c );

}

while( !s.empty() ) {

op = s.pop();

add op to postfix string;

}

First we will declare a stack ‘s’. The ‘while loop’ will continue till the end of input. We read the input character and store it in the ‘c’. Here the input character does not mean one character, but an operand or an operator. Then we have a conditional if statement. If ‘c’ is an operand, then we will have to add it to postfix string. Whenever we get an operand in the infix form, it will be added to the postfix form. The order of operands does not change in the conversion. However, in this case, the order of operators may change. If ‘c’ is the operator, then we will, at first, check that stack is not empty besides identifying the precedence of the operators between the input operator and the operator that is at the top of the stack. In case of the precedence of the operator that is on the stack is higher, we will pop it from the stack and send to the postfix string. For example if we have * on the stack and the new input operator is +. As the precedence of the + operator is less than the * operator, the operands of the multiplication has already been sent to the postfix expression. Now, we should send the * operator to the postfix form. The plus operator (+) will wait. When the while loop sends all such operators to the postfix string, it will push the new operator to the stack that is in ‘c’. It has to wait till we get the second operand. Then we will again get the input. On the completion of the input, the while loop will be finished. There may be a case that input may be completed even at the time when there are still some elements on the stack. These are operators. To check this, we have another while loop. This loop checks if the stack is not empty, pops the operator and put it in the postfix string. Let’s take a look at a comprehensive example to understand it. In case of the infix expression, A + B * C, we have three columns, one each for input symbol, the postfix expression and the stack respectively. Now let’s execute the pseudo code. First of all, we get the ‘A’ as input. It is an operand so we put it on the postfix string. The next input is the plus operator (+) which will be pushed on the stack. As it is an operator and we need two operands for it. On having a look at the expression, you might have figure out that the second operand for the plus operator is B*C. The next input is the operand B being sent to the postfix expression form. The next thing we get is the input element as ‘*’. We know that the precedence of * is higher than that of the +. Let’s see how we can do that according to our pseudo code. The prcd(s.top(), op) takes two operands. We will get the top element of the stack i.e. + will be used as first argument. The second argument is the input operator i.e. *. So the function call will be as prcd(+, *) while the function returns false because the precedence of the plus operator is not higher than the multiplication operator. So far, we have only one operand for multiplication i.e. B. As multiplication is also a binary operator, it will also have to wait for the second operand. It has to wait and the waiting room is stack. So we will push it on the stack. Now the top element of the stack is *. The next symbol is ‘C’. Being an operand, C will be added to the postfix expression. At this point, our input expression has been completed. Our first ‘while loop’ executes till the end of input. After the end of the input, the loop will be terminated. Now the control goes to the second while loop which says if there is something on the stack, pop it and add it the postfix expression. In this case, we have * and + on the stack. The * is at the top of the stack. So when we pop, we get * which is at the top of the stack and it will be added to the postfix expression. In the result of second pop, we get the plus operator (+) which is also added to the postfix expression. The stack is empty now. The while loop will be terminated and postfix expression is formed i.e. ABC*+.

Symbol	postfix	stack
A	A
+	A	+
B	AB	+
*	AB	* +
C	ABC	* +
	ABC*	+
	ABC*+

If we have to convert the infix expression into the postfix form, the job is easily done with the help of stack. The above algorithm can easily be written in C++ or C language, specially, if you already have the stack class. Now you can convert very big infix expressions into postfix expressions. Why we have done this? This can be understood with the help of the example of spreadsheet programming where the value of cell is the evaluation of some expression. The user of the spreadsheets will use the infix expressions as they are used to it.

Sometimes we do need the parenthesis in the infix form. We have to evaluate the lower precedence operator before the higher precedence operator. If we have the expression (A+B) *C, this means that we have to evaluate + before the multiplication. The objective of using parenthesis is to establish precedence. It forces to evaluate the expression first of all. We also have to handle parenthesis while converting the infix expression into postfix one. When an open parenthesis ‘(‘ is read, it must be pushed on the stack. This can be done by setting prcd(op,‘(‘ ) to be FALSE. What is the reason to put the parenthesis on the stack? It is due to the fact that as long as the closing parenthesis is not found, the open parenthesis has to wait. It is not a unary or binary operator. Actually, it is a way to show or write precedence. We can handle the parenthesis by adding some extra functionality in our prcd function. When we call prcd(op, ‘(‘), it will return false for all the operators and be pushed on the stack. Also, prcd( ‘(‘,op ) is FALSE which ensures that an operator after ‘(‘ is pushed on the stack. When a ‘)’ is read. All operators up to the first ‘(‘ must be popped and placed in the postfix string. To achieve this our function prcd( op,’)’ ) should return true for all the operators. Both the ‘(‘ and the’)’ will not go to the postfix expression. In postfix expression, we do not need parenthesis. The precedence of the operators is established in such a way that there is no need of the parenthesis. To include the handling of parenthesis, we have to change our algorithm. We have to change the line s.push(c) to:

if( s.empty() || symb != ‘)’ )
s.push( c );

else
s.pop(); // discard the ‘(‘

If the input symbol is not ‘)’ and the stack is not empty, we will push the operator on the stack. Otherwise, it is advisable to pop the stack and discard the ‘(‘. The following functionality has to be added in the prcd function.

prcd( ‘(‘, op ) = FALSE for any operator

prcd( op, ‘)’ ) = FALSE for any operator other than ‘)’

prcd( op, ‘)’ ) = TRUE for any operator other than ‘(‘

prcd( ‘)’, op ) = error for any operator.

Conversion from infix to postfix

During the process of conversion, there may be need of parenthesis in the infix especially at the times when we want to give a higher precedence to an operator of lower precedence. For example, if there is a + operator and * operator in an expression and a programmer wants the execution of addition before the multiplication. To achieve this object, it is necessary to put parentheses around the operands of + operator. Suppose, there is the expression A + B * C in which we want to give the precedence to the + operator over * operator. This expression will be written as (A + B) * C. Now we are going to discuss the conversion of infix expression that includes parentheses to the postfix expression. We have defined the return values for opening ‘(‘and closing ‘)’ parentheses in the precedence function. Let’s try to understand this process with the help of an example of converting the infix expression (A + B) * C into a postfix expression. We will see how our algorithm, discussed earlier, converts this infix expression into a postfix expression. To carry out the process of conversion we have three columns symbol, postfix and stack. The column symbol has the input symbols from the expression. The postfix column has the postfix string (expression) after each step and the stack is used to put the operators on it. The whole process of converting the infix notation into a postfix is given in the following table. This process of conversion is completed in eight steps. Each of the rows of the table depicts one step.

Step No.	Symbol	Postfix	Stack
1	(		(
2	A	A	(
3	+	A	(+
4	B	AB	(+
5	)	AB+
6	*	AB+	*
7	C	AB+C	*
8		AB+C*

First of all, there is the input symbol ‘(‘(i.e. opening parenthesis). As this is not an operand, it may be put on the stack. The next input symbol is ‘A’. Being an operand it goes to the postfix string and the stack remains unchanged. Then there is + operator of binary type. Moreover, there is one operand in the postfix string. We push this + operator on the stack and it has to wait for its second operand. Now in the input symbol, there is an operand ‘B’. We put his operand in the postfix string. Then after this, there is the closing parenthesis ‘)’ in the input symbol. We know that the presence of a closing parenthesis in the input means that an expression (within the parentheses) has been completed. All of its operands and operators are present with in the parentheses. As studied in the algorithm, we discard a closing parenthesis when it comes in the input. Then the operators from the stack are popped up and put in the postfix string. We also pop the opening parenthesis and discard it as we have no need of opening as well as closing parenthesis in the postfix notation of an expression. This process is carried out in the 5^th row of the table. The + operator is put in the postfix string. We also discard the opening parenthesis, as it is not needed in the postfix.

Now the next input symbol is *. We put this operator on the stack. There is one operand for the * operator i.e. AB+. The * operator being a binary operator, has to wait for the second operand. ‘C’ is the Next input symbol that is an operand. We put it in the postfix string. After this, the input string (expression) ends so we come out of the loop. We check if there is any thing on the stack now? There is * operator in the stack. We pop the operator and put it into the postfix string. This way, we get the postfix form of the given infix expression that becomes AB+C*. In this postfix expression, the + operator is before the * operator. So addition operation is done before the multiplication. This is mainly due to the fact that in the infix expression, we have put parentheses to give + operator the precedence higher than the * operator. Note that there are no parentheses in the postfix form of the given infix expression.

Now we apply the evaluation algorithm on this postfix expression (i.e. AB+C*). The two operands A and B, will go to the stack. Then operator + will pop these operands from the stack, will add them and push the result back on the stack. This result becomes an operand. Next ‘C’ will go to the stack and after this * operator will pop these two operands (result of addition and C). Their multiplication will lead to the final result. The postfix notation is simple to evaluate as compared to the infix one. In postfix, we need not to worry about what operation will be carried first. The operators in this notation are in the order of evaluation. However, in the infix notation, we have to force the precedence according to our requirement by putting parentheses in the expression. With the help of a stack data structure, we can do the conversion and evaluation of expressions easily.

Technorati Tags: Infix to postfix conversion,Infix to postfix conversion through stack,stack implementation of Infix to postfix conversion,solution of Infix to postfix conversion,data structure and algorithm tutorial,data structure tutorial,programming,infix postfix conversion,infix postfix expression