【LeetCode】数据结构题解（10）[有效的括号]

😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘
所属专栏：玩转数据结构题型❤️
🚀 >博主首页：初阳785❤️
🚀 >代码托管：chuyang785❤️
🚀 >感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️
🚀 >博主也会更加的努力，创作出更优质的博文！！❤️
🚀 >关注我，关注我，关注我，重要的事情说三遍！！！！！！！！❤️
😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘

😉 1.题目来源

LeetCode有效的括号
🚨注意：本题涉及到有关数据结构——栈，这一章节的知识点，如有小伙伴还不熟栈的，可以先复习复习一下有关栈的相关知识，复习的地方我也提供了哦🙂，所用到的知识点——栈
🚨注意：同样的本题是使用纯C语言实现的.

👀2.题目描述

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

🚨🚨🚨🚨🚨🚨🚨🚨🚨

• 🚨注意:像一下的测试用例也是返回false的哦
  💡: 输入: “( { ) }”;
  💡: 输出:false
  虽然这个有匹配的括号,但是这个是不行的,要满足,匹配一对括号后并拿掉这块括号后,后面的括号还能匹配才行.

• 💡: 输入: “[ ( { } ) ]”
  💡: 输出:true
  这个便可以.

🤔3.解题思路

• 🤔当看到这个题目的时候,我们一开始的想法肯定是,通过一个数组把所有的括号存起来,在对数组遍历,通过判断是左括号来给其遍历找到右括号,直到所有括号都匹配完比,如果是这样的话,空间复杂度是O(1),时间复杂度是O(n^2),这样看起来是可以的🤔实则是一个错误的思路,因为我们遍历的时候,虽然所有的括号都匹配成功了,但是😱可能括号的顺序是错误的,就比如:"( { ) }" 或者再如"} { ] [ ) ("这些虽然遍历结束后,得到的都是所有括号都可以匹配成功,但是😮他们顺序是错误的,故返回false
• 既然匹配成功的同时还要求要顺序不能乱我们就想到了,栈的特殊特点(先进的后出),于是我们就遍历数组,如果遇到的是左括号,我们就入栈,如果遇到的是右括号,我们就出栈匹配,这样根据栈的特性,就很好解决了括号的顺序问题.

💡例一:

💡例二:

🚨🚨🚨🚨🚨🚨🚨🚨🚨
🚨注意: 除了上面的情况之外,还可能遇到两种情况

• 💡1.右括号多了
  如果是左括号多了的话,栈中有又没有括号了,直接返回false

• 💡2.左括号多了
  如果是右括号多了,就是栈中还有括号,二数组中没有与之匹配的括号了,同样返回false

🥳4.代码展示

//调用栈接口
typedef char STDataType;
typedef struct Stack
{STDataType* data;int capaciyt;int size;
}Stack;void StackInit(Stack* ps);void StackDestroy(Stack* ps);void StackPush(Stack* ps, STDataType x);void StackPop(Stack* ps);STDataType StackTop(Stack* ps);bool StackEmpt(Stack* ps);int StackSize(Stack* ps);void StackInit(Stack* ps)
{assert(ps);ps->data = NULL;ps->capaciyt = 0;ps->size = 0;
}void StackDestroy(Stack* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->capaciyt = ps->size = 0;
}void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps->size == ps->capaciyt){int newCapacity = ps->capaciyt == 0 ? 4 : ps->capaciyt * 2;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc");exit(-1);}ps->data = tmp;ps->capaciyt = newCapacity;}ps->data[ps->size] = x;ps->size++;
}void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpt(ps));ps->size--;
}STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpt(ps));return ps->data[ps->size - 1];
}bool StackEmpt(Stack* ps)
{assert(ps);return ps->size == 0;
}int StackSize(Stack* ps)
{assert(ps);return ps->size;
}//函数实现
bool isValid(char * s)
{Stack st;//记得初始化StackInit(&st);while (*s){//如果是左括号就入栈if (*s == '[' || *s == '(' || *s == '{'){StackPush(&st,*s);}//如果是右括号，就出栈对比else{//如果是左括号更多,栈内数据为空,直接返回falseif (StackEmpt(&st)){StackDestroy(&st);return false;}char ch = StackTop(&st);StackPop(&st);if ((*s == ']' && ch != '[') || (*s == ')' && ch != '(') || (*s == '}' && ch != '{')){StackDestroy(&st);return false;}}s++;}//如果是右括号更多,栈中数据不为空,同样返回falsebool ret = StackEmpt(&st);StackDestroy(&st);return ret;
}