题目

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

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

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

数据

  1. 示例 1:
  2. 输入: "()"
  3. 输出: true
  5. 示例 2:
  6. 输入: "()[]{}"
  7. 输出: true
  9. 示例 3:
  10. 输入: "(]"
  11. 输出: false
  13. 示例 4:
  14. 输入: "([)]"
  15. 输出: false
  17. 示例 5:
  18. 输入: "{[]}"
  19. 输出: true
  21. 示例 6:
  22. 输入: "["
  23. 输出: false
  25. 示例 7:
  26. 输入: "]"
  27. 输出: false

题解

  1. 创建一个栈，把所有左括号入栈
  2. 遇到右括号，判断栈顶的括号是否与此右括号匹配，不匹配返回false，匹配则将匹配的左括号出栈

  3. 如果都匹配，则栈最终是空的。如果栈不为空，说明输入的是奇数个括号，一定有不匹配的，则返回false

    代码

    ``` public class ValidParentheses {

    private Stack stack = new Stack<>();

    public boolean isValid(String s) {

    1.  for (int i = 0; i < s.length(); i++) {
    2.      if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
    3.          stack.push(s.charAt(i));
    4.      } else if (s.charAt(i) == ')') {
    5.          if (stack.isEmpty()||stack.peek() != '(')
    6.              return false;
    7.          else
    8.              stack.pop();
    9.      } else if (s.charAt(i) == '}') {
    10.          if (stack.isEmpty()||stack.peek() != '{')
    11.              return false;
    12.          else
    13.              stack.pop();
    14.      } else if (s.charAt(i) == ']') {
    15.          if (stack.isEmpty()||stack.peek() != '[')
    16.              return false;
    17.          else
    18.              stack.pop();
    19.      }
    20.  }
    21.  if(!stack.isEmpty())
    22.      return false;
    23.  return true;

    } }

```