前言

在前端算法面试中，经常会被问到的一道题是 - “有效的括号”或者是称呼为“字符串是否是括号匹配”，什么意思呢？

判断一个字符串s中，括号是是否是成对、按顺序出现的，如果满足条件返回 true，否则返回false。

一个有效的字符串，必需同时满足以下条件：

• 左括号必须用相同类型的右括号闭合。

• 左括号必须以正确的顺序闭合。

举个🌰：

1. 字符串s = '(a(b)[c])'，是有效的，符合上述规则；

2. 字符串s = '(a{b(})c])'，是无效的，虽然都闭合了，但是顺序是不正确的，不符合上述规则；

很多小伙伴在第一次遇到这个问题的时候，都会考虑去进行遍历，查询匹配第一个括号，然后在倒序查询对应的括号，诸如此类的操作，都是南辕北辙，费力不讨好的。

这道面试题非常的基础也非常的经典，主要考察的是面试者对栈这种数据结构的理解。

如果你想到了栈这种数据结构，其实这道题就非常简单了。

小课堂：

栈是一种特殊的逻辑结构，有个特点：在栈中的元素遵循了先进后出，后进先出的特点。

算法实现思路

在字符串遍历的过程中，如果是遇到了左括号，进行入栈操作，如果是遇到了右括号则与当前栈顶元素(即数组的最后一个元素)进行比对，是否是对应匹配的，若匹配，则进行出栈操作，不匹配此刻即可以表示当前字符串不是有效的括号匹配。如果是一直匹配的，执行出栈操作，最终栈内的元素长度肯定是0。我们以字符串s = '(a(b)[c])'举例来说明:

以数组的形式实现栈结构，声明const arr = []，遍历字符串s

1. 遇到左括号(，执行入栈，则arr = ['(']；

2. 遇到字符a，直接跳到不执行任何操作；

3. 遇到左括号(，执行入栈，则arr = ['(', '(']；

4. 遇到字符b，直接跳过不执行任何操作；

5. 遇到右括号)，与栈顶元素执行比对，二者是对应的，执行出栈操作，此处arr = ['(']；

6. 遇到左括号[，执行入栈操作，则arr = ['(', '[']；

7. 遇到字符c，直接跳过不执行任何操作；

8. 遇到右括号]，与栈顶元素执行比对，二者是对应的，执行出栈操作，此处arr = ['(']；

9. 遇到右括号)，与栈顶元素执行比对，二者是对应的，执行出栈操作，此处arr = []；

10. 判断数组arr的长度为0，得出结果，当前字符串s是有效的括号匹配。

基于以上的逻辑思路，我看来看下代码实现：

/**
 * @method isValid
 * @description 判断字符串s是否是有效括号匹配
 * @param s string 待判断字符串
 * @returns boolean
 */
function isValid(s: string): boolean {
  const len = s.length;
  const arr: string[] = [];
  // 临界值判断
  if (!len) {
    return true;
  }
  // 遍历字符串s
  for (let i = 0; i < len; i++) {
    switch (s[i]) {
      // 左括号 - 入栈
      case '(':
      case '{':
      case '[':
        arr.push(s[i]);
        break;
      // 右括号
      case ')':
        // 比对栈顶元素是(，当前元素是)
        // 不匹配，直接返回false
        // 匹配，执行出栈
        if (arr.pop() !== '(') return false;
        break;
      case '}':
        // 比对栈顶元素是{，当前元素是}
        // 不匹配，直接返回false
        // 匹配，执行出栈
        if (arr.pop() !== '{') return false;
        break;
      case ']':
        // 比对栈顶元素是[，当前元素是]
        // 不匹配，直接返回false
        // 匹配，执行出栈
        if (arr.pop() !== '[') return false;
        break;
      default:
        break;
    }
  }
  return !arr.length;
}