匹配有效的括号——栈的使用

栈是一种以列表存储信息的数据结构，它遵循LIFO（Last In First Out）模式。它不允许按照顺序来添加或删除元素，只能遵循LIFO模式。你可以想象桌面上有一叠纸，只能往上堆放或拿取纸张，不能从中间或底部拿取纸张。只要确认元素遵循LIFO模式，栈就可以派上用场。下面是常见的栈的使用场景：

JavaScript的调用栈
在各种编程语言中管理函数调用
许多程序提供的撤销重做功能
括号匹配的校验

下面是括号匹配的例子：给定一个包含"(" ")" "[" "]" "{" "}"的字符串s，判断其是否合法的括号匹配。

要使字符串匹配，需要满足以下条件：

左括号必须用相同类型的右括号闭合
括号必须用正确的顺序闭合
每个有括号必须有一个相同类型的左括号

实现思路：

将字符串转化为数组
遍历数组中的括号部分，如果能和栈顶的字符匹配则出栈；如果不能匹配则入栈。
最后判断栈是否为空，如果为空则表示括号匹配，否则括号不匹配。

const checkString = (s) => {
  const stack = [];
  const baseString = s.split('');
  const codes = ['(', ')', '[', ']', '{', '}'];

  for (let i = 0; i < baseString.length; i++) {
    const index = codes.indexOf(baseString[i]);

    // 先判断是否匹配到了括号一部分，根据不同的括号找到对应的匹配符号，如果匹配则出栈，不匹配则入栈。
    // 只有先左括号，后右边符号才算匹配
    if (index > -1) {
      if (index % 2 === 0) {
        stack.unshift(baseString[i]);
      } else {
        if (stack[0] === codes[index - 1]) {
          stack.shift();
        } else {
          stack.unshift(baseString[i]);
        }
      }
    }
  }

  return stack.length === 0;
};

console.log(checkString('()[]{}')); // true