题目介绍:
声明:题目来源于力扣.
题目链接:传送门
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例
示例1:
输入：s = “()” 输出：true
示例2:
输入：s = “()[]{}” 输出：true
示例3:
输入：s = “(]” 输出：false
解题思路:
此题我们使用’栈’这个结构.
每个左括号都与右边最近的右括号匹配。所以我们可以用栈来保存每个等待匹配的右括号的左括号是什么，只要匹配成功就把元素弹出，当字符串遍历结束时如果栈为空，就说明所有括号都互相匹配了。那么这个字符串就是有效的。
例如:
情况1:(右括号过多或者未匹配)
字符串没有遍历结束,而遇到右括号时,栈已经为NULL,则直接返回false.
当0 ,1 ,2入栈.
3与2匹配成功,则2出栈.
4与1匹配成功,则1出栈.
5与0匹配成功,0出栈.
此时6为右括号,在栈顶并没有等到他想要的人,因为栈已经为NULL了,则返回false.
情况2:
左字符串依次入栈,右字符串依次出栈,最后字符遍历结束,而栈也是空栈,则表示括号匹配成功.
当0 ,1 ,2 ,3入栈.
4与3匹配成功,则3出栈.
5与2匹配成功,则2出栈.
6与1匹配成功,则1出栈.
7与0匹配成功,则0出栈.
此时栈为NULL,且字符串遍历结束.返回true.
情况3:(左括号过多或者未匹配成功)
左括号过多,即使右括号用完(这个例子没用完),字符串遍历结束,栈中仍有元素(左括号未找到匹配).
栈非空返回false.
步骤:
在C语言中使用栈的结构,需要自己造轮子,先设计一个栈出来,文章结尾已经写出,其次是一定要记得初始化(InitST).
- 计算字符串的长度
- 如果字符串是长度为奇数,则直接返回
false. - 遇见左括号入栈
- 遇见右括号先判断栈是否为
NULL,为空则直接返回false.
不为空,则与栈顶元素比较,如果是匹配成功的则出栈,否则直接返回false - 最后如果栈是
NULL栈则返回true,否则返回false
代码实现:
bool isValid(char* s) { ST st1; InitST(&st1);//这个别忘了 int sz=strlen(s); if (sz % 2 == 1) { return false; } for(int i=0;i<sz;i++) { if(s[i]=='('||s[i]=='['||s[i]=='{')//左括号进栈 { STPush(&st1,s[i]); } else//右括号 { if(STEmpty(&st1))//如果碰到右括号,且栈是NULl,则返回false { return false; } //如果栈顶与右括号匹配,则出栈 if (STTop(&st1) == '(' && s[i] == ')' || STTop(&st1) == '[' && s[i] == ']' || STTop(&st1) == '{' && s[i] == '}')//如果栈顶元素与右括号匹配,则出栈 { STPop(&st1); } else{ return false; } } } return STEmpty(&st1); }
上面的实现方式还有一个内存泄漏的危险,因为栈空间并没有被释放,应当在每个返回结果之前调用栈销毁函数(STDestory).
栈的实现:
//栈的实现 //oj题里面不需要写头文件 typedef char stacktype; typedef struct stack { stacktype* data; int top; int capacaity; }ST; void InitST(ST* ps); void STPush(ST* ps, stacktype x);//压栈 void STPop(ST* ps);//出栈 bool STEmpty(ST* ps);//判断是否为空栈 stacktype STTop(ST* ps);//返回栈顶元素 void STDestory(ST* ps);//栈的销毁 //初始化栈 void InitST(ST* ps) { assert(ps); ps->top = -1; ps->capacaity = 4; ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype)); } //压栈 void STPush(ST* ps, stacktype x) { assert(ps); if (ps->top + 1 == ps->capacaity) { ps->capacaity *= 2; stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype)); if (tmp == NULL) { printf("增容失败\n"); } ps->data = tmp; } ps->top++; ps->data[ps->top] = x; } //出栈 void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } //判断是否为空栈,是空返回真 bool STEmpty(ST* ps) { assert(ps); if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1; { return true; } return false; } //返回栈顶元素 stacktype STTop(ST* ps) { assert(ps); return ps->data[ps->top];//反追栈顶元素 } //栈的销毁 void STDestory(ST* ps) { assert(ps); free(ps->data);//释放栈空间 ps->data = NULL; ps->top = -1; ps->capacaity = 0; }
提交记录:
