前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >括号匹配算法「建议收藏」

括号匹配算法「建议收藏」

作者头像
全栈程序员站长
发布2022-07-28 20:18:38
6240
发布2022-07-28 20:18:38
举报

大家好,又见面了,我是你们的朋友全栈君。

概述

​ 括号匹配在很多字符串处理的场景中时常被用到,诸如各大IDE括号不匹配的错误提示,编译器编译时检查应该成对出现的括号是否符合要求等,在这里我们就直接使用一种比较常规,但效率不差的方法去解决括号匹配的问题就行了。

栈方法匹配问题

​ 为了方便描述,对于需要做匹配的两个符号,比如’(‘和’)’,前者可称为左侧符号,后者可称为右侧符号。在做符号匹配时,如果以左侧符号为标准,左侧符号需要右侧符号来完成匹配,但是由于诸如括号这类的符号可以做嵌套,所以左侧符号之后既能有左侧符号,也能有右侧符号,处理起来很麻烦。以右侧符号为标准就没有这个问题了,每一个右侧符号都需要一个左侧符号来匹配,并且要求该右侧符号之前最近的一个符号必须是相匹配的左侧符号,这样处理起来就方便多了。

​ 利用栈可以很容易地解决这个问题,在遍历字符串时,若当前位置是右侧符号,那它需要一个该位置之前最近的一个符号为左侧符号,否则不匹配。定义一个栈,用以记录遍历到当前位置时,所遇到的左侧符号,处理方式是这样的,每当遇到一个右侧符号时,检查栈是否为空,若此时栈不为空,则对栈进行pop操作表明顶部元素已被匹配,否则为不匹配情况,直接返回false。当整个字符串遍历结束,我们就可以通过判断该栈是否为空来判断整个字符串中的符号是否匹配。具体代码如下:

Code

代码语言:c++
复制
bool is_match(const string &str)
{
    size_t len = str.length();
    stack<char> s;
    int i;
    for (i = 0; i < len; ++i) {
        if (str[i] == '(') {
            s.push(str[i]);
            continue;
        }
        if (str[i] == ')') {
            if (!s.empty() && s.top() == '(') {
                s.pop();
                continue;
            }
        }
    }

    if (!s.empty()) {
        return false;
    }

    return true;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/129081.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年4月1,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 概述
  • 栈方法匹配问题
  • Code
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档