力扣:有效的括号

2023-12-20 06:30:01

? PS:此程序和注释由:Ayor大佬写出

题目:

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

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

示例?2:

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

示例?3:

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

提示:

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

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

char pairs(char a);
bool isValid(char* s);

int main() {
? ? printf("%d\n", isValid("({)}"));
? ? return 0;
}

char pairs(char a) {
? ? if (a == '}') return '{';
? ? if (a == ']') return '[';
? ? if (a == ')') return '(';
? ? return 0;
}

bool isValid(char* s) {
? ? int lenth = strlen(s); // 获取字符串长度
? ? if (lenth % 2 == 1) { ? // 假如长度为奇数,则括号一定不匹配,所以直接返回False
? ? ? ? return false;
? ? }
? ? char stk[lenth + 1], top = 0; // 新建一个堆栈,用来存放可能出现的括号 top则是堆栈的下标,也是用来存储括号的对数
? ? for (int i = 0; i < lenth; i++) {
? ? ? ? char ch = pairs(s[i]); ?//
? ? ? ? /* 通过调用paris函数得知配对的括号
? ? ? ? ?* 因为正括号一定在前面,所以对正括号配对无意义,所以递入pairs的一定是反括号
? ? ? ? ?* 如果递入的是正括号则会返回0, 如果递入反括号则会返回对应的正括号 */
? ? ? ? if (ch) {
? ? ? ? ? ? /* 这是一个很关键的地方,因为只有正括号全部存入堆栈中才有可能进入这个if
? ? ? ? ? ? ?* 假设开始输入的是反括号就会进入if,则会因为top为0则直接进入下面的if中返回false
? ? ? ? ? ? ?* 假设输入的是正括号就因为上面的ch会返回0不会进入这个if,会进入到下面的else中的内容 */
? ? ? ? ? ? if (top == 0 || stk[top - 1] != ch) {
? ? ? ? ? ? ? ? /* 如果top为0,则括号开始就为反括号
? ? ? ? ? ? ? ? ?* 如果堆栈的前一个不是对应的括号,例如s[i]为')',但stk[top - 1]为'['则不匹配,也会进入if */
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? ? ? top--;
? ? ? ? ? ? // top--就是堆栈中的下标向前推,例如堆栈中是'[','{',这在判断'}'和'{'配对后不会进入上面的if继续判断'['是否配对
? ? ? ? } else {
? ? ? ? ? ? /* 大多数情况下,开始的是正括号,即ch=0,会进入到下面的语句
? ? ? ? ? ? ?* 下面的语句也就是将所有的正括号都存入堆栈中,然后top会自增以统计正括号的数量
? ? ? ? ? ? ?* 由于括号都是成对出现,所以top的数量也就是有多少对括号 */
? ? ? ? ? ? stk[top++] = s[i];
? ? ? ? }
? ? }
? ? // 如果top能一直减到0,则说明括号的数量是配对的,就会返回top == 0一个逻辑判断,如果top为0,则返回1,反之返回0
? ? return top == 0;
}

文章来源:https://blog.csdn.net/lzcandhyandcg/article/details/135080919
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。