《力扣题库（C）：第20题 （有效的括号）》

第二十题：有效的括号

• 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
• 有效字符串需满足：
• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

解题：

/**
 * @file 20.cpp
 * @author  HarkerYX
 * @brief   有效的括号
 * @version 0.1
 * @date 2021-04-30
 * 
 * @copyright Copyright (c) 2021
 * 
 */

/*
第二十题：有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解题思路:

能闭合肯定不是奇数，一定是偶数， 

入栈出栈
 
*/

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>


char Judge(char c)
{
    if(c == ')') return '(';
    if(c == ']') return '[';
    if(c == '}') return '{';

    return '0';
}

/**
 * @brief 
 * 
 * @param s 
 * @return true 
 * @return false 
 */
bool isValid(const char *s)
{
    int len = strlen(s);

    //奇数肯定不匹配
    if(len%2 !=0 || len <= 0)
        return false;

    //创建栈
    char *statck = (char *)malloc(sizeof(char) * len);
    int statckPos = -1; // 栈的初始位置

    while(*s!='\0'){

        char c = *s;
        if(c =='(' || c =='[' || c == '{'){
            // 入栈
            statck[++statckPos] = c;

        }
        else{
            // 栈开始就是右括号也是不匹配(可能是字符串开头就是右括号也可能是中间处理遇到)
            if(statckPos == -1)
                return false;

            char tmp = Judge(c);
            if(statck[statckPos] != tmp)
                return false;

            //匹配的话栈就后退
            statckPos--;
            
        }

        s++;
    }

    //走到这里判断完后看栈是否为空，如果为空就代表全部匹配
    if(statckPos == -1)
        return true;

    return false;
}

int main(void) 
{
    bool ret = false;
    const char *s = "()[]{}"; // 匹配
    // const char *s = "(]"; // 不匹配
    // const char *s = "([)]"; // 不匹配
    // const char *s = "{[]}"; // 匹配

    ret = isValid(s);
    printf("%s\n",ret?"匹配":"不匹配");
    return 0;
}

匹配