JS括号匹配算法中`return !stack.length`什么时候会返回true？

有效括号匹配函数返回true的逻辑说明 #

你疑惑的点本质是没搞清楚：栈在push元素后，是会因为匹配成功执行pop操作移除元素的，只要所有入栈的左括号都被正确匹配弹出，最终栈的长度就会是0，!stack.length自然就返回true。

我们拿有效括号输入"()[]{}"举例，一步步看执行过程：

• 遍历第一个字符(：属于hash中定义的左括号，执行push，此时stack = ['(']
• 遍历第二个字符)：不属于左括号，进入else分支：
  • 执行pop取出栈顶元素(，计算hash[top]得到)，和当前字符匹配，校验通过，此时stack = []
• 遍历第三个字符[：左括号入栈，stack = ['[']
• 遍历第四个字符]：匹配成功，弹出栈顶，stack = []
• 遍历第五个字符{：左括号入栈，stack = ['{']
• 遍历第六个字符}：匹配成功，弹出栈顶，stack = []

遍历完成后栈长度为0，!0的结果就是true，函数返回true。

如果括号是无效的，比如输入"(()"，遍历结束后栈里会残留一个没有被匹配的(，stack.length = 1，!1结果为false，函数返回false。

这个函数的判断逻辑其实覆盖了有效括号的两个必要条件：

• 所有右括号都有对应的、顺序正确的左括号匹配（遍历过程中不会提前返回false）
• 不存在未匹配的左括号残留（遍历结束后栈为空）

var isValid = function (s) {
  const hash = {
    '(': ')',
    '{': '}',
    '[': ']',
  };

  const stack = [];

  for (const char of s) {
    if (char in hash) stack.push(char);
    else {
      const top = stack.pop();

      if (top === undefined || hash[top] !== char) {
        return false;
      }
    }
  }

  return !stack.length;
};

内容的提问来源于stack exchange，提问作者Camerone Stoney