程序地带

20. 有效的括号


在这里插入图片描述 在这里插入图片描述 这道题就是一个括号匹配的问题,如果遍历到右半部分的符号,而前面最新的一个左半部分的符号不匹配,那就是无效的。所以我们要记录最新的括号,就要用一个先进后出的数据结构来记录左边的括号,就是栈!当s的长度为奇数直接false。遍历字符串,如果是左半部分的符号就加入栈,如果是右边的就判断栈是否空(必须要加),不加会报错,如果空就返回false,如果右半部分为’]",而栈顶不是’[’,那就是false,如果匹配,就弹出栈顶元素。其他以此类推,最后返回栈是否为空,如果为空就证明匹配完了,如果不为空,证明没匹配干净,也就是奇数个的情况


class Solution {
public:
bool isValid(string s) {
//如果在闭合之前检测到别的符号先闭合了没事
//如果在闭合之前检测到别的符号,但是别的符号没有闭合,那就是错了,匹配括号的过程是栈的操作
//如果在({[出现之前先出现)}]就是错了,或者前面的那些都被消耗光之后才出现})也是错
if(s.length() == 0) return true;
stack<char> sta;
for(int i = 0; i < s.length(); ++i){
if(s[i] == '{' || s[i] == '(' || s[i] == '['){
sta.push(s[i]);
}
else{
if(sta.empty()) return false;
if(s[i] == '}'){
if(sta.top() !='{') return false;
sta.pop();
}
else if(s[i] == ')'){
if(sta.top() != '(') return false;
sta.pop();
}
else{
if(sta.top() != '[') return false;
sta.pop();
}
}
}
return sta.empty();
}
};

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/J_avaSmallWhite/article/details/112760936

随机推荐

Linux系统(根目录下)目录介绍整理。

Linux系统(根目录下)目录介绍整理。/boot:很多Linux系统把内核映像和其他一些和启动有关的文件都放在这里。/tmp:一般只有启动时产生的临时文件才会放在这个地方。用户的临时文件都放在“/v...

??mile???i 阅读(465)

ROS学习笔记之——navigation的进一步探索

ROS学习笔记之——navigation的进一步探索

之前博客《ROS学习笔记之——NavigationStack》和《ROS学习笔记之——路径规划及avoidobstacles》已经对ROS中的navigation做了一些学习了,本博文再...

gwpscut 阅读(495)

二维码python myqr_Python利用myqr库创建自己的二维码

前言相信朋友们都看过各种群里钓鱼的涩图二维码吧(手动滑稽),今天学了一下制作方式(myqr库的使用),在这里分享一下这个整活利器。MyQR是一个能够生成自定义二维码的第三方...

weixin_39614877 阅读(350)

封装 电流密度 重布线_半导体封装及其制造方法与流程

本发明实施例涉及一种半导体封装及其制造方法。背景技术:业界已知使用连接在横向上间隔开的结合垫与焊料凸块的重布线层来制作微电子导体装置,例如半导体装置。此种装置是晶片级芯片规...

weixin_39615741 阅读(962)