首页 计算机学科 java 编程题

# 有效的括号

给定一个只包括 '(' ， ')' ， '{' ， '}' ， '[' ， ']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

# 思路分析

我么你可以从左到右的分析每一个字符，如果碰到的是左括号呢

假如遇到了一个左小括号
str : (
那么就将左括号配对的有小括号放到栈里，因为我期望将来要跟一个有小括号配对
stack : )
假如遇到了一个 左中括号
str : [
那么就将右中括号放到栈中，以此类推 这是遇到左括号的问题
stack : ]
那么如果遇到右括号呢？如果遇到右中括号，那么就将这个右中括号跟栈顶元素进行比较如果相等就说明是一个有效的括号
因为 现有 某个左括号 栈顶才会存储 某个右括号，所以遇到某个右括号就判断栈中栈顶元素括号是否一样就行了
当判断右括号相同时，就将栈中存储的 对应的右括号 移除

代码：

public boolean isValid(String s) {
   // 创建栈 用于存储 右括号
   Stack<Character> stack = new Stack<>();
   for(int i = 0; i < s.length(); i++)
   {
      // 获取 每次 第 i 个字符
      char c = s.charAt(i);
      // 判断是什么左括号 就 往栈里添加什么右括号
      if(c == '(')
      {
         stack.add(')');
      }else if(c == '[')
      {
         stack.add(']');
      }else if(c == '{')
      {
         stack.add('}');
      }else
      {
         // 先判断 栈中 是否 为 空 然后 在判断 栈 中的括号是否 等于 c 不然会报错
         if(!stack.isEmpty() && stack.peek() == c)
         {
            // 如果等于就将 合法的括号弹出 然后进行下一轮的比较
            stack.pop();
         }else
         {
            return false;
         }
      }
   }
   // 如果栈中的括号都弹出 没有了为空了 说明是合法的返回 true，否则返回
   return stack.isEmpty();
}