题解 | #有效括号序列#

若括号相匹配，则字符串长度必为偶数。

将左括号放入新栈中，若遇到的一直是左侧括号，则一直放入栈中。

然后与遇到的右侧配对，如果遇到的右侧括号和栈顶能成功匹配，则可以将栈顶元素出栈。

等待遇到下一个新的右侧括号与新的栈顶元素匹配。

如果字符串中的内容全部合法，新的栈中最后应该不含任何元素。

而右侧括号的个数也应该等于字符串长度的一半。

循环结束的判断标志：

如果匹配，栈空为标志。

不匹配则直接跳出循环。（此时不记录右括号个数不增一）

可见注释。

#include<stdbool.h>
#define INIT_SIZE 4
#define BUFFER_SIZE 8

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
typedef struct valid_stack{
    char *top;
    char *bottom;
    int size;
}set;

set *stack_init()
{
    set *new_stack=(int*)malloc(sizeof(int));
    if(new_stack==NULL)
    {
        return NULL;
    }
    new_stack->bottom=(int*)malloc(sizeof(int)*INIT_SIZE);
    new_stack->top=new_stack->bottom;
    new_stack->size=INIT_SIZE;
    
    if(new_stack->bottom==NULL)
    {
        return NULL;
    }
    
    return new_stack;
}

set *stack_push(set *stack, char p_data)
{    
    if(stack==NULL)
    {
        return NULL;
    }
    if(stack->top-stack->bottom>=stack->size)
    {
        stack->bottom=(int*)realloc(stack->bottom, (stack->size+BUFFER_SIZE)*sizeof(int));
        if(stack->bottom==NULL)
        {
            return NULL;
        }
        stack->top=stack->bottom+stack->size;
        stack->size+=BUFFER_SIZE;
    }
         *(stack->top)=p_data;
          stack->top++;
    return stack;
}

set *stack_pop(set *stack)
{
    char pop_data;
   if(stack==NULL) 
   {
       return NULL;
   }
    
         stack->top--;
         pop_data=*(stack->top);
    
       return pop_data; 
}


bool isValid(char* s ) {
    
    // write code here
    int len,flag;
    int i=0,j=0;
    char store;
    set *stack=stack_init(); 
    len = strlen(s);
    
    if(len%2)//括号对数，半括号个数，奇数直接结束。
    {
   
        return false;
    }
    else
    {
       flag=len/2;
    }
    
    for(i=0;i<len;i++)
    {
      if((*(s+i)=='(')||(*(s+i)=='[')||(*(s+i)=='{'))//左括号，入栈
      {
          stack_push(stack,*(s+i));
      }
    //比较栈顶元素和当又括号内容，若是合法括号，必然和栈顶元素相匹配 
      else
        {
    	 while(( (*(s+i)==')'&&*(stack->top-1)=='(')|| (*(s+i)==']'&&*(stack->top-1)=='[')|| (*(s+i)=='}'&&*(stack->top-1)=='{') )&&(stack!=NULL))   
        //如果括号合法，那么左右括号数各占一半。
        //不匹配则以栈空做为结束标志，防止一直陷入while。 
       {
          stack_pop(stack);//比较完的元素出栈
          j++;//记录右括号的个数

       }
        
   	  }
    }
    if(j==flag)//右半括号数等于字符串长度的一半。
      {
          return true;
      }
    else
      {
          return false;
      }
    
}