괄호 일치 M

  1 #include<stdio.h>

  2 #include<stdlib.h>

  3 #include<string.h>

  4 #define Stack_Size 100

  5 #define Stackincrement 10

  6 #define ok 1

  7 #define error 0

  8 #define overflow 2

  9 #define true 1

 10 #define false 0

 11 typedef int status;

 12 typedef struct

 13 {

 14   char *base;

 15   char *top;

 16   int stacksize;

 17 }SqStack;

 18 status InitStack(SqStack &S)

 19 {

 20   S.base=(char *)malloc(Stack_Size*sizeof(char));

 21   if(!S.base)  exit(overflow);

 22   S.top=S.base;

 23   S.stacksize=Stack_Size;

 24   return ok;

 25 }

 26 status StackEmpty(SqStack &S)

 27 {

 28   if(S.top==S.base)

 29   return true;

 30   else 

 31   return false;

 32 }

 33 status GetTop(SqStack S,char &e)

 34 {

 35   if(S.top==S.base)  return error;

 36   e=*(S.top-1);

 37   return ok;

 38 }

 39 status Push(SqStack &S,char e)

 40 {

 41   if((S.top-S.base)==S.stacksize)

 42   {

 43     S.base=(char *)realloc(S.base,(S.stacksize+Stackincrement)*sizeof(char));

 44     if(!S.base)  exit(overflow);

 45     S.top=S.base+S.stacksize;

 46     S.stacksize+=Stackincrement;

 47   }

 48   *S.top++=e;

 49   return ok;

 50 }

 51 status Pop(SqStack &S,char &e)

 52 {

 53   if(S.top==S.base)  return error;

 54   e=*--S.top;

 55   return ok;

 56 }

 57  status match(char *array) 

 58  {

 59      int i,length,state;

 60      SqStack s;

 61      char temp;

 62      state=1;i=0;length=strlen(array);

 63      InitStack(s);

 64      while(i<length&&state)

 65      {

 66          switch(array[i])

 67          {

 68              case '(':

 69              case '[':

 70              {

 71                  Push(s,array[i]);break;

 72              }

 73              case ')':

 74              {

 75                  GetTop(s,temp);

 76                  if(!StackEmpty(s)&&temp=='(')

 77                 Pop(s,temp);

 78                  else state=0;

 79                  break;

 80              }

 81              case ']':

 82              {

 83                  GetTop(s,temp);

 84                  if(!StackEmpty(s)&&temp=='[')

 85                 Pop(s,temp);

 86                  else state=0;

 87                  break;

 88              }

 89          }

 90          i++;

 91      }

 92      if(StackEmpty(s)&&state)

 93      return ok;

 94      else

 95      return error; 

 96  }

 97  int main()

 98  {

 99      int n;

100     char s[10000];

101     scanf("%d",&n);

102     getchar();

103     while(n--)

104     {

105         gets(s);

106         if(match(s))

107         puts("Yes");

108         else

109         puts("No");

110     }

111     return 0;

112 }