0404_有效的括号

Algorithm：有效的括号¶

题目描述¶

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例¶

输入: "()" ,"{[]}" ,"()[]{}"
输出: true

输入: "(]" ,"([)]"
输出: false

题目解析¶

这里使用**栈**的思想。

遍历字符串
如果当前字符是左半边括号，则入栈
如果当前字符是右半边括号，则进行判断

1）若现在栈为空，则直接返回false

2）若现在栈不为空，且栈顶元素不是对应的左半边括号，则返回false

3）若现在栈不为空，且栈顶元素刚好是对应的左半边括号，则取出栈顶，继续循环

java代码¶

    /**
     * @param str 输入的字符串
     * @return
     */
    public static boolean isValid(String str){
          Stack<Character> stack = new Stack();
          // 判断是否为空字符串
          if (str == null || str.isEmpty()) return true;

          for (int i = 0; i < str.length(); i++) {
              char s = str.charAt(i);
              // 为左半边括号时入栈
              if (s == '{' || s == '[' || s =='(') { // 注意：由于是char类型，等号右边为单引号
                  stack.push(s);
              } else { // 为右半边括号时，分情况
                  if (stack.isEmpty()) {
                      return false;
                  } else {
                      char topChar = stack.pop();
                      if (topChar == '(' && s == ')'){
                          return true;
                      } else if (topChar == '[' && s == ']'){
                          return true;
                      } else if (topChar == '{' && s == '}'){
                          return true;
                      } else {
                          return false;
                      }
                  }
              }
          }

            // 遍历结束，stack不为空时，返回false
              return stack.isEmpty();
    }