题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

示例 1:

输入: "([)]"
输出: false

示例 2:

输入: "([])"
输出: true

解析：

栈的结构，先进后出。

1. 遍历当匹配到是左括号，执行进栈操作；
2. 当匹配到右括号需要和栈顶匹配是否为相应的右括号，若为是执行出栈操作；若为否则为非有效的字符串。
3. 遍历完成后，若是空栈则为有效的字符串；若非空栈则为非有效的字符串。

有效的括号(栈的思路).png

复杂度分析：

时间复杂度：
空间复杂度：

代码

1. 数组模拟栈

       bool isValid(char * s){
           //空字符串显然符合
           if(*s == 0) return true;
           int len = strlen(s);
           //奇数长度的字符串显然不符合
           if(len & 1) return false;
       
           char stack[len];
           int top = -1;
           for(int i=0; i<len; ++i){
               //如果是左括号们，欢迎入栈
               if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                   stack[++top] = s[i];
               //不是左括号们，如果栈空则无法配对，不符合
               else if(top == -1) return false;
               //不是左括号们，栈非空，当前和栈顶配对，符合
               else if(s[i] == stack[top]+1 || s[i] == stack[top]+2)
                   stack[top--] = 0;
               //不是左括号们，栈非空，当前和栈顶不配对，不符合
               else return false;
           }
           //最后栈为空则符合，不为空则不符合
           return top == -1;
       }
   

2. 链式栈

       #define MaxSize 10
       #define bool int
       #define true 0
           #define false 1
       /**
        链式栈结点
        */
       typedef struct StackNode
       {
           char data;
           struct StackNode *next;
       }StackNode,*LinkStackNode;
       /*
         链式栈
        */
       typedef struct
       {
           LinkStackNode top;
           int length;
       }LinkStack;
       /*5.1 构造一个空栈S */
       LinkStack* InitLinkStack()
       {
           LinkStack *s = (LinkStack *)malloc(sizeof(LinkStack));
           if (s == NULL)
           {
             printf("创建失败\n");
             return NULL;
           }
           s->top=NULL;
           s->length=0;
           return s;
       }
       void push_stackNode(LinkStack *s,char value){
          LinkStackNode node = (LinkStackNode )malloc(sizeof(StackNode));
          if (node == NULL)
          {
             printf("压栈失败\n");
             return;
          }
       
          node->data = value;
          node->next = s->top;
          s->top = node;
          s->length = s->length + 1;
       }
       void pop_stackNode(LinkStack *s){
       
          if (s->length == 0)
          {
             printf("空栈\n");
             return;
          }
          LinkStackNode node = s->top;
          s->top = node->next;
          s->length--;
          free(node);
       }
       bool ismatch(char first, char second) {
           if (second - first == 1 || second - first == 2) return true;
           return false;
       }
       bool isleft(char c) {
           if (c == 40 || c == 91 || c == 123) return true;  // 左
           return false;  // 右
       }
       void ClearStack(LinkStack *S){
           LinkStackNode p,q;
           p = S->top;
           while (p) {
               q = p;
               p = p->next;
               free(q);
           }
           S->length = 0;
       }
       bool isValid(char * s){
            /* 1.初始化链表栈 */
           LinkStack *stack = InitLinkStack();
           /* 2.准备添加元素 */
           while (*s != '\0') {
               if (stack->length != 0 && ismatch(stack->top->data, *s)) {
                   pop_stackNode(stack);  // 传入二级指针
                   s++;  // 字符移动
               }else if(isleft(*s)){
                   push_stackNode(stack, *s++);
               } else{
                   return false;
               }
           }
           bool res = stack->length == 0;
           ClearStack(stack);
           return res;
   }