与栈有关：3 分钟看懂如何判断括号的合法性

你的名字 2023-06-05 05:49 64阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=png][640_wx_fmt_png]

作者 | labuladong

来源 | labuladong

对括号的合法性判断是一个很常见且实用的问题，比如说我们写的代码，编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号`[](){}`，判断起来有一点难度。

本文就来聊一道关于括号合法性判断的算法题，相信能加深你对**栈**这种数据结构的理解。

题目很简单，输入一个字符串，其中包含`[](){}`六种括号，请你判断这个字符串组成的括号是否合法。

![640?wx\_fmt=png][640_wx_fmt_png 1]

解决这个问题之前，我们先降低难度，思考一下，**如果只有一种括号****`()`**，应该如何判断字符串组成的括号是否合法呢？

### 一、处理一种括号 ###

字符串中只有圆括号，如果想让括号字符串合法，那么必须做到：

**每个右括号****`)`的左边必须有一个左括号`(`和它匹配**。

比如说字符串`()))((`中，索引为 2 和 3 的两个右括号**左边**就没有左括号匹配，所以这个括号组合是不合法的。

所以我们可以一边遍历一边记录遇到左括号的个数，每次遇到右括号就匹配一个左括号数。根据这个思路，我们可以写出算法：

![640?wx\_fmt=png][640_wx_fmt_png 2]

如果只有圆括号，这样就能正确判断合法性。对于三种括号的情况，我一开始想模仿这个思路，定义三个变量`left1`，`left2`，`left3`分别处理每种括号，虽然要多写不少 if else 分支，但是似乎可以解决问题。

但实际上直接照搬这种思路是不行的，比如说只有一个括号的情况下`(())`是合法的，但是多种括号的情况下，`[(])`显然是不合法的。

仅仅记录每种左括号出现的次数已经不能做出正确判断了，我们要加大存储的信息量，可以利用栈来模仿类似的思路。

### 二、处理多种括号 ###

栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。

我们这道题就用一个名为`left`的栈代替之前思路中的`left`变量，**遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配**。

![640?wx\_fmt=png][640_wx_fmt_png 3]

以上就是判断括号合法性的算法思路，核心就是利用了栈先进后出的特点，栈顶元素就是最近的左括号，遇到右括号就在栈顶判断就行了。遇到括号相关的问题，可以优先考虑一下是否能借助栈来解决。

![640?][640]

**有热门推荐?**

1.【程序员】

2.【GitHub】

3.【算法】

4.【数据结构】

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

[640_wx_fmt_png]: /images/20230601/d32f8c385c454ed3a9a29c7b4526cd65.png
[640_wx_fmt_png 1]: /images/20230601/ff3a6c1a1573468793d17e89530741b0.png
[640_wx_fmt_png 2]: /images/20230601/dcba5ff1a3c9496c8a2e61df17273af1.png
[640_wx_fmt_png 3]: /images/20230601/f82e7f5a003b4b9a8e016bd9e271d163.png
[640]: /images/20230601/048382d98a724997a9b5598d13bf9c8e.png
[640_wx_fmt_jpeg]: /images/20230601/945c40b421824e28b22005b7ed3b96b0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，64人围观）

还没有评论，来说两句吧...

相关阅读

相关带你一分钟看懂 “Docker”

2010年，几个搞IT的年轻人，在美国旧金山成立了一家名叫“dotCloud”的公司。这家公司主要提供基于PaaS的云计算技术服务。具体来说，是和LXC有关的容器技术。

向右看齐/ 2024年02月19日 11:04/ 0 赞/ 88 阅读

相关与栈有关：3 分钟看懂如何判断括号的合法性

点击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![640?wx\_fmt=png][640_wx_fmt_png] 作者 | labu

你的名字/ 2023年06月05日 05:49/ 0 赞/ 65 阅读

相关 [数据结构与算法]有效的括号（判断括号是否匹配），栈，字典

var isValid = function (s) { if (s.length % 2 === 1) {

Bertha 。/ 2022年12月06日 04:17/ 0 赞/ 147 阅读

相关两分钟看懂有效的括号

大家好，我是程序员吴师兄，今天跟大家分享一道和栈有关的题目，超级简单也超级容易理解，这道题目曾经出现在 bilibili 的面试中。 ![d47ace51870392b0

悠悠/ 2022年11月10日 14:13/ 0 赞/ 189 阅读

相关判断元素入栈/出栈的合法性

判断元素入栈出栈的合法性：验证进栈出栈的合法性---每次取栈顶元素，因为出栈的时候先进后出，每次出栈的总是栈顶元素，栈顶元素和另一个数组进行对比，如果相等就pop

曾经终败给现在/ 2022年09月23日 05:56/ 0 赞/ 207 阅读

相关利用栈判断括号是否匹配

update on 20210826 主要思想使用栈进行匹配，但是不要把所有的字符都入栈，只需要将三种括号入栈即可，这样会简化控制逻辑。代码如下： i

素颜马尾好姑娘i/ 2022年06月17日 05:14/ 0 赞/ 233 阅读

相关判断元素出栈、入栈顺序的合法性

元素出栈、入栈顺序的合法性。如：入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1），则合法。入栈的序列（1,2,3,4,5），出栈序列为（4,5,2,3,1

ゝ一纸荒年。/ 2022年06月12日 11:39/ 0 赞/ 259 阅读

相关【架构】3分钟看懂架构演变

小编带您看世界。架构演变过程：阶段一、单机集中构建网站 ![这里写图片描述][70] 阶段二、应用服务器集群随着访问量增加，单台应用服务器无法满足需求，假

比眉伴天荒/ 2022年05月15日 04:48/ 0 赞/ 239 阅读

相关 3分钟带你看懂android中的Binder机制

一.引言最近一段时间由于工作，接触到framework部分比较多一点，也难免要和Binder打一些交道，也整理了一些相关知识，但准备写这篇文章时，还是有些慌。而且关于整

àì夳堔傛蜴生んèń/ 2022年03月06日 05:54/ 0 赞/ 266 阅读

相关菜鸟3分钟看懂flex布局

[3分钟看懂flex布局][3_flex] 首先要有个容器，并设置display:flex;display:-webkit-flex;该容器有以下六个属性： <tabl

快来打我*/ 2021年09月18日 02:50/ 1 赞/ 768 阅读