带你读《图解算法小抄》十七、栈（4）

带你读《图解算法小抄》十七、栈（3）https://developer.aliyun.com/article/1348077?groupCode=tech_library

4.有效的括号

给定一个只包含字符'('，')'，'{'，'}'，'['和']'的字符串str，判断该字符串中的括号是否有效。

为了判断括号是否有效，需满足以下条件：

• 左括号必须用相同类型的右括号闭合。
  
• 左括号必须以正确的顺序闭合。
  

注意空字符串也被视为有效。

示例：

输入：str = "()" 输出：true 解释：括号字符串"()"是有效的。

输入：str = "()[]{}" 输出：true 解释：括号字符串"()[]{}"是有效的。

输入：str = "(]" 输出：false 解释：括号字符串"(]"是无效的，左括号必须用相同类型的右括号闭合。

输入：str = "([)]" 输出：false 解释：括号字符串"([)]"是无效的，左括号必须以正确的顺序闭合。

1）题目分析与解题步骤：

这个问题可以使用栈来解决。我们可以遍历字符串中的每个字符，并使用一个栈来模拟括号的匹配过程。对于每个字符，我们根据其类型进行操作。

解题步骤如下：

创建一个栈stack，用于模拟括号的匹配过程。

遍历字符串str中的每个字符，并执行以下操作：

如果当前字符是左括号(，{或[，则将其入栈。

如果当前字符是右括号)，}或]，则需要进行匹配操作。

如果栈为空，或栈顶元素与当前字符不匹配，则返回false，表示括号无效。

如果栈顶元素与当前字符匹配，将栈顶元素出栈，继续遍历下一个字符。

遍历完整个字符串后，如果栈为空，则表示括号有效，返回true；否则，表示括号无效，返回false。

2）JavaScript解题框架：

function isValid(str) {
  let stack = new Stack();
  for (let char of str) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else if (char === ')' || char === '}' || char === ']') {
      if (stack.isEmpty() || !isMatching(stack.pop(), char)) {
        return false;
      }
    }
  }
  return stack.isEmpty();
}
function isMatching(left, right) {
  return (
    (left === '(' && right === ')') ||
    (left === '{' && right === '}') ||
    (left === '[' && right === ']')
  );
}

在这个框架中，我们首先定义了一个栈类Stack，其中包含了常用的栈操作方法。然后，我们使用栈来判断括号是否有效。

在isValid函数中，我们遍历字符串str，并根据字符的类型进行判断和操作。如果当前字符是左括号，将其入栈；如果当前字符是右括号，则进行匹配操作。

匹配操作通过isMatching函数来判断栈顶元素与当前字符是否匹配。如果栈为空，或栈顶元素与当前字符不匹配，则返回false，表示括号无效。

最后，判断栈是否为空，如果为空，则表示括号有效，返回true；否则，表示括号无效，返回false。

带你读《图解算法小抄》十七、栈（5）https://developer.aliyun.com/article/1348075?groupCode=tech_library