前端算法 === 栈的拿手好戏！| 20 有效的括号

本文主要是介绍前端算法 === 栈的拿手好戏！| 20 有效的括号，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题外话

进入正题

题解

优化版本

题外话

括号匹配是使用栈解决的经典问题。

题意其实就像我们在写代码的过程中，要求括号的顺序是一样的，有左括号，相应的位置必须要有右括号。

如果还记得编译原理的话，编译器在词法分析的过程中处理括号、花括号等这个符号的逻辑，也是使用了栈这种数据结构。

再举个例子，linux系统中，cd这个进入目录的命令我们应该再熟悉不过了。

cd a/b/c/../../

这个命令最后进入a目录，系统是如何知道进入了a目录呢，这就是栈的应用（其实可以出一道相应的面试题了）

所以栈在计算机领域中应用是非常广泛的。

有的同学经常会想学的这些数据结构有什么用，也开发不了什么软件，大多数同学说的软件应该都是可视化的软件例如APP、网站之类的，那都是非常上层的应用了，底层很多功能的实现都是基础的数据结构和算法。

所以数据结构与算法的应用往往隐藏在我们看不到的地方！

这里我就不过多展开了，先来看题。

进入正题

由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有几种情况。

一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。

建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。

先来分析一下这里有三种不匹配的情况，

第一种情况，字符串里左方向的括号多余了，所以不匹配。

括号匹配1

第二种情况，括号没有多余，但是括号的类型没有匹配上。

括号匹配2

第三种情况，字符串里右方向的括号多余了，所以不匹配。

括号匹配3

我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出动手之前分析好题目的重要性。

动画如下：

20.有效括号.gif

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

分析完之后，代码其实就比较好写了，

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

题解

/*** @param {string} s* @return {boolean}*/
var isValid = function (s) {let stack = [];for (let i = 0; i < s.length; i++) {const char = s[i];// 检查是否是左括号，如果是，则压入栈中if (char === "(" || char === "{" || char === "[") {stack.push(char);} else {// 如果栈为空，但遇到了右括号，说明序列无效if (stack.length === 0) {return false;}// 检查栈顶的左括号与当前的右括号是否匹配let top = stack[stack.length - 1];if ((char === ")" && top === "(") ||(char === "}" && top === "{") ||(char === "]" && top === "[")) {stack.pop(); // 匹配成功，弹出栈顶元素} else {return false; // 不匹配，序列无效}}}// 如果栈为空，则所有括号都正确匹配，序列有效return stack.length === 0;
};console.log(isValid("()[]{}")); // 应该输出 true

优化版本

函数使用一个栈 stack 来跟踪最近遇到的左括号，以及一个映射 map 来确定每个左括号对应的右括号。

在 for 循环中，如果遇到一个左括号（"("、"{" 或 "["），它会被推入栈中。如果遇到一个右括号，函数会尝试从栈中弹出一个元素，并检查这个弹出的元素是否是对应的左括号。如果不是，或者栈已经为空但还有右括号，函数将返回 false。

例子中，调用 isValid("(}") 时，字符串 "(}" 包含一个左括号 "(" 和一个错误的右括号 "}". 当遇到右括号 "}", 栈中应该弹出一个左括号 "{" 来匹配它，但栈中实际上是 "("。因此，map[stack.pop()] 将不会等于 "}", 函数将返回 false。