題目

給定一個(gè)只包括 '('，')'帆疟，'{'鹉究，'}'，'['踪宠，']' 的字符串自赔，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號(hào)必須用相同類型的右括號(hào)閉合柳琢。
2. 左括號(hào)必須以正確的順序閉合绍妨。
3. 注意空字符串可被認(rèn)為是有效字符串。

示例 1:

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

示例 2:

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

解析：

棧的結(jié)構(gòu)柬脸，先進(jìn)后出他去。

1. 遍歷當(dāng)匹配到是左括號(hào)，執(zhí)行進(jìn)棧操作肖粮；
2. 當(dāng)匹配到右括號(hào)需要和棧頂匹配是否為相應(yīng)的右括號(hào)孤页，若為是執(zhí)行出棧操作；若為否則為非有效的字符串涩馆。
3. 遍歷完成后行施，若是空棧則為有效的字符串；若非空棧則為非有效的字符串魂那。

有效的括號(hào)(棧的思路).png

復(fù)雜度分析：

時(shí)間復(fù)雜度：
空間復(fù)雜度：

代碼

1. 數(shù)組模擬棧

       bool isValid(char * s){
           //空字符串顯然符合
           if(*s == 0) return true;
           int len = strlen(s);
           //奇數(shù)長(zhǎng)度的字符串顯然不符合
           if(len & 1) return false;
       
           char stack[len];
           int top = -1;
           for(int i=0; i<len; ++i){
               //如果是左括號(hào)們蛾号，歡迎入棧
               if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                   stack[++top] = s[i];
               //不是左括號(hào)們，如果椦难牛空則無(wú)法配對(duì)鲜结，不符合
               else if(top == -1) return false;
               //不是左括號(hào)們，棧非空活逆，當(dāng)前和棧頂配對(duì)精刷，符合
               else if(s[i] == stack[top]+1 || s[i] == stack[top]+2)
                   stack[top--] = 0;
               //不是左括號(hào)們，棧非空蔗候，當(dāng)前和棧頂不配對(duì)怒允，不符合
               else return false;
           }
           //最后棧為空則符合，不為空則不符合
           return top == -1;
       }
   

2. 鏈?zhǔn)綏?

       #define MaxSize 10
       #define bool int
       #define true 0
           #define false 1
       /**
        鏈?zhǔn)綏＝Y(jié)點(diǎn)
        */
       typedef struct StackNode
       {
           char data;
           struct StackNode *next;
       }StackNode,*LinkStackNode;
       /*
         鏈?zhǔn)綏?     */
       typedef struct
       {
           LinkStackNode top;
           int length;
       }LinkStack;
       /*5.1 構(gòu)造一個(gè)空棧S */
       LinkStack* InitLinkStack()
       {
           LinkStack *s = (LinkStack *)malloc(sizeof(LinkStack));
           if (s == NULL)
           {
             printf("創(chuàng)建失敗\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.初始化鏈表?xiàng)?*/
           LinkStack *stack = InitLinkStack();
           /* 2.準(zhǔn)備添加元素 */
           while (*s != '\0') {
               if (stack->length != 0 && ismatch(stack->top->data, *s)) {
                   pop_stackNode(stack);  // 傳入二級(jí)指針
                   s++;  // 字符移動(dòng)
               }else if(isleft(*s)){
                   push_stackNode(stack, *s++);
               } else{
                   return false;
               }
           }
           bool res = stack->length == 0;
           ClearStack(stack);
           return res;
   }