2022年6月12日leetcode每日一题打卡——20.有效的括号

20.有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

输入：s = "()"
输出：true

输入：s = "()[]{}"
输出：true

输入：s = "(]"
输出：false

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

其实际考察的内容应当是栈的应用，括号的匹配检验是栈的应用。如果要运用栈的话需要定义栈的结构类型，还得初始化栈并将字符串s以此压入栈中，如此会导致运行用时与内存消耗过大，因此在这里我们尝试运用数组来代替栈，由于字符串的大小未知，为了通过所有测试用例，将数组的大小设置得较大一些。接着要注意栈顶指针top指向真正的栈顶元素之上的下标地址这一特性，接着将左括号全部压栈直至遇到有括号，将栈顶元素与第一个出现的有括号依次匹配，如果匹配成功则出栈，也就是top指针下移并与下一个右括号进行匹配直至全部匹配成功top=0或者中途不匹配return false。最后以top是否等于0为判断是否匹配成功的标志，因为有可能括号的个数是单数，就导致top！=0。

1、定义大小足够大的字符数组stack来代替栈，用以存储字符串中的左括号。
2、定义top作为栈顶指针，初始化为0，top==0是栈空的标志。
3、利用for循环以此访问字符串中的每个括号，如果是左括号将其压入栈（存入数组），并且让top指针上移。如果不是左括号则首先判断是否栈空，接着对栈顶元素调用switch函数，与右括号进行匹配，如果匹配不成功则代表字符串无效，匹配成功则看下一个括号，以此对字符串进行遍历。
4、此时判断top是否等于0，如果等于0就代表整个字符串都匹配成功，字符串有效，return true；如果不等于0就代表匹配失败，字符串无效,return false（有可能有3个左括号和2个有括号导致top最后不等于0，因此也是无效的。）。

想要了解运用栈来实现括号匹配的算法思想即具体算法描述可以看这部分内容——括号匹配的检验。

bool isValid(char * s){
    char stack[100000];//运用数组模拟栈
    int top=0;//栈顶指针
    for(int i=0;s[i]!='';i++)//把左括号存入数组（压栈）
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')
        {
            stack[top]=s[i];//存入之后，记得top指针是指向真正的栈顶元素之上的下标地址，所以存入后要top++
            top++;
        }
        else//不为左括号则看是否能于目前的进行匹配
        {
            if(top==0)//栈为空
              return false;
              switch(stack[top-1])//top-1才是指向栈顶元素的
              {//以此判断是否能于栈顶元素进行匹配，如果不能则代表字符串无效
                  case '(':
                  {
                      if(s[i]==')')
                        top--;
                      else
                        return false;
                        break;
                  }
                  case '[':
                  {
                      if(s[i]==']')
                       top--;
                      else
                       return false;
                      break;
                  }
                  case '{':
                  {
                      if(s[i]=='}')
                        top--;
                      else
                        return false;
                      break;
                  }
              }
        }
    }
    return top==0;//此时如果top=0则代表匹配成功，字符串有效
}