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

全栈程序员-站长 • 2022年4月13日上午7:00 • 未分类 • 阅读 60

概述括号匹配在很多字符串处理的场景中时常被用到，诸如各大IDE括号不匹配的错误提示，编译器编译时检查应该成对出现的括号是否符合要求等，在这里我们就直接使用一种比较常规，但效率不差的方法去解决括号匹配的问题就行了。栈方法匹配问题为了方便描述，对于需要做匹配的两个符号，比如’(‘和’)’，前者可称为左侧符号，后者可称为右侧符号。在做符号匹配时，如果以左侧符号

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

概述

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

栈方法匹配问题

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

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

Code

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.net/129081.html原文链接：https://javaforall.net

赞 (0)

全栈程序员-站长

0 0

CMS-CMS框架解析[通俗易懂]

CMS-CMS框架解析[通俗易懂] 今天第一次接触到CMS的项目，当时是修改一个别人项目的BUG，说实话，我开始并不了解这是一个开源框架，我开始以为是一个别人字节写的自用框架，而非公共的开源框架。其实本人也写过微框架，本次就借助CMS来谈谈框架的思想。框架的本质框架的本质，自我理解就是从URL输入到数据处理到数据输出的过程，如果输出的是页面HTML则是传统的MVC模式，如果输出的是JSON的数据集…

全栈程序员-站长
2022年5月25日
28
一文搞懂基因融合（gene fusion）的定义、产生机制及鉴定方法[通俗易懂]

一文搞懂基因融合（gene fusion）的定义、产生机制及鉴定方法[通俗易懂]一般来说，基因融合是指基因组层面的融合。但转录组层面也可能发生融合，主要是由于两个不同基因转录产生的RNA，由于某种原因融合在了一起，形成新的融合RNA，该RNA可能编码蛋白，也可能为非编码。而基因组

全栈程序员-站长
2022年8月6日
2
java帝国的崛起[通俗易懂]

java帝国的崛起[通俗易懂]1C语言帝国的统治现在是公元1995年，C语言帝国已经统治了我们20多年，实在是太久了。 1972年，随着C语言的诞生和Unix的问世，帝国迅速建立统治，从北美到欧洲，从欧洲到亚洲，无数程序员臣服在他的脚下。帝国给我们提供了极好的福利：贴近硬件，运行极快，效率极高。使用这些福利…

全栈程序员-站长
2022年9月24日
0
微信小程序视频下载软件_如何禁用微信小程序

微信小程序视频下载软件_如何禁用微信小程序1.在标签里传递ID<textcatchtap=”handleDownload”data-link=”{{item.link}}”>下载</text>2.js下载方法//下载handleDownload(e){letlink=e.currentTarget.dataset.link;let…

全栈程序员-站长
2022年4月19日
38
Django（2）python虚拟环境virtualenvwrapper[通俗易懂]

Django（2）python虚拟环境virtualenvwrapper[通俗易懂]python虚拟环境虚拟环境（virtualenvironment），它是一个虚拟化，从电脑独立开辟出来的环境。通俗的来讲，虚拟环境就是借助虚拟机来把一部分内容独立出来，我们把这部分独立出来的东西

全栈程序员-站长
2022年7月29日
3
TensorFlow 安装教程

趁着十一放假期间，有这么一点空闲时间，自己看了些tensorflow的资料，顺便在自己的机器上安装了一下tensorflow的环境。安装过程还算比较顺利，现在跟大家分享一下。1.准备好Anaconda环境tensorflow是属于很高层的应用。高层应用的一个比较大的麻烦就是需要依赖的底层的东西很多，如果底层依赖没有弄好的话，高层应用是没法玩转的。在极客学院有关tensorflow的教程中，提到了

全栈程序员-站长
2022年4月9日
34

发表回复

关注全栈程序员社区公众号