Algorithms Design | Index

Well-formed sequence of parentheses and brackets

[Statement of the exercise]  If the code of the wellformed function operates the stack directly, it makes more sense to treat stk and t as local variables:

#define N 100

// This function returns 1 if a string s contains
// a well-formed sequence of parentheses and
// brackets and returns 0 if the sequence is
// malformed.

int wellformed (char s[]) {
   char stk[N]; int t; 
   int i;

   t = 0;
   for (i = 0; s[i] != '\0'; ++i) {
      // stk[0..t-1] is a stack of '(' and '['
      switch (s[i]) {
         case ')': if (t == 0) return 0;
                   if (stk[--t] != '(') return 0; 
                   break;
         case ']': if (t == 0) return 0;
                   if (stk[--t] != '[') return 0; 
                   break;
         default:  stk[t++] = s[i];
      }
   }
   return t == 0;
}