前端算法 === 栈的专长好戏！| 20 有用的括号

目录
题外话
进入正题
题解
优化版本

---

题外话


括号匹配是使用栈解决的经典问题。
题意其实就像我们在写代码的过程中，要求括号的顺序是一样的，有左括号，相应的位置必须要有右括号。
如果还记得编译原理的话，编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑，也是使用了栈这种数据结构。
再举个例子，linux系统中，cd这个进入目录的命令我们应该再熟悉不外了。

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

复制代码

这个命令末了进入a目录，系统是怎样知道进入了a目录呢 ，这就是栈的应用（其实可以出一道相应的口试题了）
以是栈在盘算机范畴中应用是非常广泛的。

---

有的同学经常会想学的这些数据结构有什么用，也开辟不了什么软件，大多数同学说的软件应该都是可视化的软件比方APP、网站之类的，那都是非常上层的应用了，底层很多功能的实现都是基础的数据结构和算法。
以是数据结构与算法的应用每每隐藏在我们看不到的地方！
这里我就不外多睁开了，先来看题。

进入正题


由于栈结构的特别性，非常得当做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种环境。
一些同学，在口试中看到这种题目上来就开始写代码，然后就越写越乱。
建议要写代码之前要分析好有哪几种不匹配的环境，如果不动手之前分析好，写出的代码也会有很多问题。

---

先来分析一下 这里有三种不匹配的环境，
第一种环境，字符串里左方向的括号多余了 ，以是不匹配。

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

第三种环境，字符串里右方向的括号多余了，以是不匹配。

我们的代码只要覆盖了这三种不匹配的环境，就不会出问题，可以看出 动手之前分析好题目的紧张性。
动画如下：

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

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
分析完之后，代码其实就比较好写了，
   但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简朴的多了！
  题解

1. /**
2. * @param {string} s
3. * @return {boolean}
4. */
5. var isValid = function (s) {
6.   let stack = [];
7.   for (let i = 0; i < s.length; i++) {
8.     const char = s[i];
9.     // 检查是否是左括号，如果是，则压入栈中
10.     if (char === "(" || char === "{" || char === "[") {
11.       stack.push(char);
12.     } else {
13.       // 如果栈为空，但遇到了右括号，说明序列无效
14.       if (stack.length === 0) {
15.         return false;
16.       }
17.       // 检查栈顶的左括号与当前的右括号是否匹配
18.       let top = stack[stack.length - 1];
19.       if (
20.         (char === ")" && top === "(") ||
21.         (char === "}" && top === "{") ||
22.         (char === "]" && top === "[")
23.       ) {
24.         stack.pop(); // 匹配成功，弹出栈顶元素
25.       } else {
26.         return false; // 不匹配，序列无效
27.       }
28.     }
29.   }
30.   // 如果栈为空，则所有括号都正确匹配，序列有效
31.   return stack.length === 0;
32. };
34. console.log(isValid("()[]{}")); // 应该输出 true

复制代码

优化版本

函数使用一个栈 stack 来跟踪最近碰到的左括号，以及一个映射 map 来确定每个左括号对应的右括号。
在 for 循环中，如果碰到一个左括号（"("、"{" 或 "["），它会被推入栈中。如果碰到一个右括号，函数会尝试从栈中弹出一个元素，并查抄这个弹出的元素是否是对应的左括号。如果不是，或者栈已经为空但还有右括号，函数将返回 false。
例子中，调用 isValid("(}") 时，字符串 "(}" 包含一个左括号 "(" 和一个错误的右括号 "}". 当碰到右括号 "}", 栈中应该弹出一个左括号 "{" 来匹配它，但栈中实际上是 "("。因此，map[stack.pop()] 将不会等于 "}", 函数将返回 false。
   在 JavaScript 中，return 语句不但会返回一个值，还会立刻退出当前函数的执行，包罗退出当前的循环。在 isValid 函数中，一旦 return false 被执行，函数将立刻克制执行并返回 false，循环也会随之竣事。
   

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。