Algorithms Design | Index

Direct stack manipulation in infix-to-postfix code

[Statement of the exercise]  The function infixToPostfix can operate the stack directly (without calling the stack manipulation functions).  In this case, it makes more sense to let the variables stk and t be local:

// The function below receives an infix expression inf
// and returns the corresponding postfix expression.

char *infixToPostfix (char inf[]) {
   char *post; 
   char *stk; int t;
   int N, i, j;

   N = strlen (inf);
   post = malloc ((N+1) * sizeof (char));
   stk = malloc (N * sizeof (char));
   t = 0;
   stk[t++] = inf[0];
   for (j = 0, i = 1; inf[i] != '\0'; ++i) {
      // stk[0..t-1] is a stack of bytes
      switch (inf[i]) {
         char x;
         case '(': stk[t++] = inf[i];
                   break;
         case ')': while ((x = stk[--t]) != '(')   
                      post[j++] = x;
                   break;
         case '+': 
         case '-': while ((x = stk[t-1]) != '(') { 
                      post[j++] = x;
                      --t;
                   }
                   stk[t++] = inf[i];
                   break;
         case '*':
         case '/': while ((x = stk[t-1]) != '(' 
                          && x != '+' && x != '-') { 
                      post[j++] = x;
                      --t;
                   }
                   stk[t++] = inf[i];
                   break;
         default:  post[j++] = inf[i];
      }
   }
   free (stk);
   post[j] = '\0';      
   return post;
}  

The while in cases ')', '-', and '/' implements a so-called n-and-a-half loop.