20. 有效的括号

题目连接：https://leetcode-cn.com/problems/valid-parentheses/
难度：简单
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

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

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

当遍历字符串遇到"{" "(" "["就入栈 遇到 "]" ")" "}"就和上一个括号进行匹配：

• "}" -> "{"
• "]" -> "["
• ")" -> "("

如果匹配成功，"{" "(" "["就出栈，也就是top--,类似消消乐，如果匹配失败则返回false
当所有字符的括号被遍历完，栈为空即top=0则返回true
这里我是用一个数组做的栈，由于是用C语言写的，数组的大小并不能进行动态变化，所有需要提前定义一个较大的数组。

bool isValid(char * s){ 
    int top = 0;//用来计栈的下标，进栈加1，出栈减1
    int i = 0;//用来计字符的下标索引
    int n = strlen(s);//计算字符长度
    if (n % 2 == 1) {//字符串的括号的长度为奇数直接返回false
        return false;
    }
    int arr[n + 1];//用一个长度为字符串长度的数组定义栈
    while (s[i])
    {
        switch (s[i])
        {
        case '(':
        case '[':
        case '{':
            arr[top] =s[i];//入栈
            top++;//数组索引加1
            break;
        case ')':
            if ( top < 1 || top >= 1 && arr[top-1] != '('  )//这里和上一个括号进行匹配，top < 1是栈已经为空没有括号可以进行对比，也直接返回false
            {
                return false;
            }
            top--;//出栈
            break;
        case ']':
            if ( top < 1 || top >= 1 && arr[top-1] !='[')
            {
                return false;
            }
            top--;
            break;
        case '}':
            if( top < 1 || top >= 1 && arr[top-1] != '{')
            {
                return false;
            }
            top--;
            break;
        }
        i++;
    }
    return top == 0 ? true : false;
}