文章目录

• 前言
• 1.题目以及分析
• 2.参考代码

  ---

  前言

  前面我们学习了栈的相关操作，现在我们做一道题，进行巩固

  Leetcode—有效的括号

  ---

  1.题目以及分析

  

  这道题就可以使用栈进行操作，因为把最左边的括号当成栈底，最右边的是栈顶，其中每种左括号(例如{，（，[ )），进行入栈，把右括号（例如( }，），] )）这些跟前面的括号进行匹配，如果没有匹配上，那就是false。

  最后，判断时候有多余的括号，然后再返回。

  2.参考代码

  typedef struct Stack{
      char*arr;
      int top;
      int capacity;
  }Stack;
  void StackInit(Stack *ps){
      ps->arr=NULL;
      ps->top=ps->capacity=0;
  }
  void StackDestory(Stack*ps){
      free(ps->arr);
      ps->arr=NULL;
      ps->top=ps->capacity=0;
  }
  void StackPush(Stack *ps,char x){
      if(ps->capacity==ps->top){
          int newCapacity=ps->capacity==0?4:2*ps->capacity*sizeof(int);
          char*tmp=(char*)realloc(ps->arr,newCapacity*sizeof(char));
          ps->arr=tmp;
          ps->capacity=newCapacity;
      }
      ps->arr[ps->top]=x;
      ps->top++;
  }
  bool StackEmpty(Stack*ps){
      return ps->top==0;
  }
  void StackPop(Stack*ps){
      ps->top--;
  }
  char StackTop(Stack*ps){
      return ps->arr[ps->top-1];
  }
  bool isValid(char* s) {
      Stack sk;
      StackInit(&sk);
      while(*s){
          if(*s=='['||*s=='{'||*s=='('){
              StackPush(&sk,*s);
          }else{
              if(StackEmpty(&sk)){
                  StackDestory(&sk);
                  return false;
              }
              char top=StackTop(&sk);
              StackPop(&sk);
              if((top=='{'&&*s!='}')
              ||(top=='['&&*s!=']')
              ||(top=='('&&*s!=')')){
                  StackDestory(&sk);
                  return false;
              }
              
          }
          s++;
      }
      bool ret=StackEmpty(&sk);
      StackDestory(&sk);
      return ret;
  }