Working with Queues | Stack and Queue Data Structure

Data Structure Tutorial / By
Working with Queues
One of the applications of the stack is in expression evaluation. A complex assignment statement such as a = b + c*d/e–f may be interpreted in many different ways. Therefore, to give a unique meaning, the precedence and associativity rules are used. But still it is difficult to evaluate an expression by computer in its present form, called the infix notation. In infix notation, the binary operator comes in between the operands. A unary operator comes before the operand. To get it evaluated, it is first converted to the postfix form, where the operator comes after the operands. For example, the postfix form for the expression a*(b–c)/d is abc–*d/. A good thing about postfix expressions is that they do not require any precedence rules or parentheses for unique definition. So, evaluation of a postfix expression is possible using a stack-based algorithm.
Program
Convert an infix expression to prefix form. 
#include <stdio.h>
#include <string.h>
#include <ctype.h>


#define N 80




typedef enum {FALSE, TRUE} bool;




#include "stack.h"


#include "queue.h"




#define NOPS 7




char operators [] = "()^/*+-";


int priorities[] = {4,4,3,2,2,1,1};


char associates[] = " RLLLL";




char t[N]; char *tptr = t; // this is where prefix will be saved.


int getIndex( char op ) {


    /*


     * returns index of op in operators.


     */


    int i;


    for( i=0; i<NOPS; ++i )


        if( operators[i] == op )


               return i;


    return -1;


}


int getPriority( char op ) {


    /*


     * returns priority of op.


     */


    return priorities[ getIndex(op) ];


}




char getAssociativity( char op ) {


    /*


     * returns associativity of op.


     */


    return associates[ getIndex(op) ];


}




void processOp( char op, queue *q, stack *s ) {


    /*


     * performs processing of op.


     */


    switch(op) {


       case ')':


              printf( "\t S pushing )...\n" );


              sPush( s, op );


              break;


       case '(':


              while( !qEmpty(q) ) {


                     *tptr++ = qPop(q);


                     printf( "\tQ popping %c...\n", *(tptr-1) );


              }


              while( !sEmpty(s) ) {


                     char popop = sPop(s);


                     printf( "\tS popping %c...\n", popop );


                     if( popop == ')' )


                            break;


                     *tptr++ = popop;


              }


              break;


       default: {


              int priop;    // priority of op.


              char topop;   // operator on stack top.


              int pritop;   // priority of topop.


              char asstop;  // associativity of topop.


              while( !sEmpty(s) ) {


                     priop = getPriority(op);


                     topop = sTop(s);


                     pritop = getPriority(topop);


                     asstop = getAssociativity(topop);


if( pritop < priop || (pritop == priop && asstop == 'L')


    || topop == ')' ) // IMP.


                      break;


                 while( !qEmpty(q) ) {


                        *tptr++ = qPop(q);


                 printf( "\tQ popping %c...\n", *(tptr-1) );


                 }


                 *tptr++ = sPop(s);


                 printf( "\tS popping %c...\n", *(tptr-1) );


         }


         printf( "\tS pushing %c...\n", op );


         sPush( s, op );


         break;


      }


   }


}


bool isop( char op ) {


    /*


     * is op an operator?


     */


    return (getIndex(op) != -1);


}




char *in2pre( char *str ) { /*


     * returns valid infix expr in str to prefix.


     */


    char *sptr;


    queue q = {NULL};


    stack s = NULL;


    char *res = (char *)malloc( N*sizeof(char) );


    char *resptr = res;


    tptr = t;


    for( sptr=str+strlen(str)-1; sptr!=str-1; -sptr ) {


       printf( "processing %c tptr-t=%d...\n", *sptr, tptr-t );


       if( isalpha(*sptr) ) // if operand.


              qPush( &q, *sptr );


       else if( isop(*sptr) )      // if valid operator.


              processOp( *sptr, &q, &s );


       else if( isspace(*sptr) )    // if whitespace.


              ;


       else {


              fprintf( stderr, "ERROR:invalid char %c.\n", *sptr );


              return "";


       }


   }


   while( !qEmpty(&q) ) {


       *tptr++ = qPop(&q);


       printf( "\tQ popping %c...\n", *(tptr-1) );


   }


   while( !sEmpty(&s) ) {


       *tptr++ = sPop(&s);


       printf( "\tS popping %c...\n", *(tptr-1) );


   }


   *tptr = 0;


   printf( "t=%s.\n", t );


   for( -tptr; tptr!=t-1; -tptr ) {


      *resptr++ = *tptr;


   }


   *resptr = 0;




   return res;


}




int main() {


    char s[N];




    puts( "enter infix freespaces max 80." );


    gets(s);


    while(*s) {


       puts( in2pre(s) );


       gets(s);


    }




   return 0;


}










Output



























Elucidation











    

  1. In an infix expression, a binary operator separates its operands (a unary operator precedes its operand). In a postfix expression, the operands of an operator precede the operator. In a prefix expression, the operator precedes its operands. Like postfix, a prefix expression is parenthesis-free, that is, any infix expression can be unambiguously written in its prefix equivalent without the need for parentheses.
    2. 

  2. To convert an infix expression to reverse-prefix, it is scanned from right to left. A queue of operands is maintained noting that the order of operands in infix and prefix remains the same. Thus, while scanning the infix expression, whenever an operand is encountered, it is pushed in a queue. If the scanned element is a right parenthesis (‘)’), it is pushed in a stack of operators. If the scanned element is a left parenthesis (‘(‘), the queue of operands is emptied to the prefix output, followed by the popping of all the operators up to, but excluding, a right parenthesis in the operator stack.
    3. 

  3. If the scanned element is an arbitrary operator o, then the stack of operators is checked for operators with a greater priority then o. Such operators are popped and written to the prefix output after emptying the operand queue. The operator o is finally pushed to the stack.
    4. 

  4. When the scanning of the infix expression is complete, first the operand queue, and then the operator stack, are emptied to the prefix output. Any whitespace in the infix input is ignored. Thus the prefix output can be reversed to get the required prefix expression of the infix input.
    5. 












Example




If the infix expression is a*b + c/d, then different snapshots of the algorithm, while scanning the expression from right to left, are shown in the Table below

















Scanning the infex expression a*b+c/d from right to left






STEP
REMAINING EXPRESSION
SCANNED ELEMENT
QUEUE OF OPERANDS
STACK OF OPERATORS
PREFIX OUTPUT




0
a*b+c/d
nil
empty
empty
nil




1
a*b+c/
d
d
empty
nil




2
a*b+c
/
d
/
nil




3
a*b+
c
d c
/
nil




4
a*b
+
empty
+
dc/




5
a*
b
b
+
dc/




6
a
*
b
* +
dc/




7
nil
a
b a
* +
dc/




8
nil
nil
empty
empty
dc/ba*+















The final prefix output that we get is dc/ba*+ whose reverse is +*ab/cd, which is the prefix equivalent of the input infix expression a*b+c*d. Note that all the operands are simply pushed to the queue in steps 1, 3, 5, and 7. In step 2, the operator / is pushed to the empty stack of operators.









In step 4, the operator + is checked against the elements in the stack. Since / (division) has higher priority than + (addition), the queue is emptied to the prefix output (thus we get ‘dc’ as the output) and then the operator / is written (thus we get ‘dc/’ as the output). The operator + is then pushed to the stack. In step 6, the operator * is checked against the stack elements. Since * (multiplication) has a higher priority than + (addition), * is pushed to the stack. Step 8 signifies that all of the infix expression is scanned. Thus, the queue of operands is emptied to the prefix output (to get ‘dc/ba’), followed by the emptying of the stack of operators (to get ‘dc/ba*+’).














Points to remember











    

  1. A prefix expression is parenthesis-free.
    2. 

  2. To convert an infix expression to the postfix equivalent, it is scanned from right to left. The prefix expression we get is the reverse of the required prefix equivalent.
    3. 

  3. Conversion of infix to prefix requires a queue of operands and a stack, as in the conversion of an infix to postfix.
    4. 

  4. The order of operands in a prefix expression is the same as that in its infix equivalent.
    5. 

  5. If the scanned operator o1 and the operator o2 at the stack top have the same priority, then the associativity of o2 is checked. If o2 is right-associative, it is popped from the stack.
    6.