Stacks->Applications

Well, we'll see here, its role in converting an infix to a postfix expression. The rest of them I've some how covered in other parts of my tutorial. So here we go....

An INFIX expression is nothing but any regular expression having operators in between operands; and obviously, the POSTFIX is the one with operands followed by their respective operators. I'll take an example...

If a/b-c*d is your infix expression then ab/cd*- will be its postfix form. How ?...Let's see.

First step is to apply brackets to the expression following the BODMAS rule; then just move the operators to their respective closing brackets. The resultant is your Postfix expression. Remember, this is the manual way of doing it.

((a/b)-(c*d))  ==>

==> ab/cd*-

Now, where does Stack figure out in between? Well, when the computer has to do this conversion, it makes use of Stack. See how..

Algorithm:-
Step-1: Check whether the current element in the expression is an operator or operand. If its an operand then go to step-2 or else step-3
Step-2: Put the element in the Postfix output stream and go for the next element in the expression, if any
Step-3: a. find the priority of that operator
            b. if the operator's priority > priority of Stack's top then push that operator inside the
                stack and go for the next element; or else pop the stack, write that value to the
                Postfix output stream and go to start of this step
Step-4: Empty the Stack and put the popped values to the output stream directly

C implementation:-
/*This is just a broad outline of the exact implementation. The actual implementation is downloadable*/
char[] infix_to_postfix(char *expr)
{
 static char out[], i;
 while(*expr != NULL)
 {
 if(*expr == OPERAND) /*step-1*/
      { out[i] = *expr; i = i+1;}    /*step-2*/
   else
      { /*step-3*/
       while(priority(*expr) <=  priority(stack[top]))
        {
         out[i] = pop( );
         i = i + 1;
        }
        push(*expr);
      }
 expr++;
 }
 while( top != -1) /*step-4*/
   { out[i] = pop( ); i++;}
 return(out);
}

Note:- I have deliberately hidden lot many implementation details like - stack details, push-pop operations; how to check for an OPERAND; how to set priority for the operators; bottom of the stack should have the least priority, etc. Please, try to fill up these gaps, believe me its really very interesting or else download the complete implementation and carefully study it.

Related Operations:
Concept
Array Implementation - Push() and Pop()
Linked List Implementation - Push() and Pop()
Application of Stacks