C语言力扣刷题10——有效的括号——[栈]

一、博客声明

  找工作逃不过刷题，为了更好的督促自己学习以及理解力扣大佬们的解题思路，开辟这个系列来记录。代码可能不是自己写的，不求方法最好，只求更多地理解大佬们的解题思路。

二、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

三、解题思路

  对于这种类似括号匹配的题目，可以采用 栈 的思路来做。

1、知识补充

 a、什么是栈（Stack）

  栈：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

  栈顶（Top）：线性表允许进行插入删除的那一端。
  栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
  空栈：不含任何元素的空表。

2、思路说明

  1、首先括号两两匹配，因此数组长度对2取余等于1的话，就可以返回false了；
  2、利用栈的后进先出原理，右括号的左边肯定有对应的左括号，就可以抵消，如果不是就返回false；

四、解题代码（附注释）

//建立匹配，识别到右括号，就变成左括号，方便判断。否则返回0
char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {//True成立的条件之一是长度为偶数
        return false;
    }
    int stk[n + 1];//用数组建立一个栈
    int top = 0;//栈顶
    for (int i = 0; i < n; i++) { //遍历整个数组
        char ch = pairs(s[i]);
        if (ch) {//判断是否识别到右括号
            if (top == 0 || stk[top - 1] != ch) {//如果不匹配，直接返回false
                return false;
            }
            top--;//出栈
        } else {
            stk[top++] = s[i];//入栈
        }
    }
    return top == 0;//遍历完整个数组，若栈顶位置位于栈地，说明符合条件
}