有效括号序列

有效括号序列

https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tqId=726&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

有效括号序列

思路:

由于需要进行括号匹配,由于对于最晚的进入的待匹配的括号是最早进行匹配的,所以符合后入先出的结构,所以用一个栈进行辅助

图解:

链接

代码:

class Solution {
public:
    //由于需要进行括号匹配,由于对于最晚的进入的待匹配的括号是最早进行匹配的
    //所以符合后入先出的结构,所以用一个栈进行辅助
    bool isValid(string s) {
        stack<char>s1;
        //遍历字符串,只要遇到左括号,就将其对应的右括号压入栈中,等待匹配
        //之后如果遇到右括号,就进行判断是否与栈顶元素一致,如果一致就表示
        //能进行匹配,再将栈顶的这个已经匹配的括号出栈
        //如果匹配的时候发现栈是空的,就表明没有对应的括号进行匹配,返回false
        for(int i=0;i<s.length();i++){
            if(s[i]=='('){
                s1.push(')');
            }else if(s[i]=='{'){
                s1.push('}');
            }else if(s[i]=='['){
                s1.push(']');
            }else if(s1.empty()){
                return false;
            }else if(s1.top()==s[i]){
                s1.pop();
            }
        }
        //最后如果字符串是合法的,就一定能够完全匹配,最后栈为空,则表示合法的串
        return s1.empty();
    }
};
全部评论

相关推荐

华泰证券信息技术部 软开 月base2.2w,年终要看当年收益,HR讲往年应届平均35W
点赞 评论 收藏
分享
落叶随风呀:学校不好就放两栏,专业能力往前移, 政治面貌不是党员不如不写,籍贯湖南衡阳,或者湖南,浅尝辄止 基本信息排版不够美观,没有对齐 简历上花里胡哨的东西去掉 项目我不评价,因为我能力有限,且对mcu了解不足 但是这份简历掌握的水平,你可以海投试试,工作没问题但是工资应该不会高,因为搞mcu的小公司多
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务