20. 有效的括号

#20. 有效的括号

题目描述

解题思路
这个也是数据结构讲栈和队列时候的必讲题吧，所以一拿到就想到用栈去做，如果时左括号就入栈，右括号就出栈一个看其是否匹配，如果不匹配或者最后栈不为空，就表明括号表达式无效。看评论之后发现有个改进的地方：如果时左括号，不直接把左括号入栈，而是把对应的右括号入栈，这样出栈之后可以直接比较是否相同，更加方便。

public boolean isValid(String s) {
  Stack<Character> stack=new Stack<>();        //1.empty()栈是否为空        
  for (int i = 0; i < s.length(); i++) {
   	char c = s.charAt(i);
   	switch (c) {
	   case '(':   //遇到左括号则把对应的右括号入栈
	    stack.push(')');break;
	   case '[':
	    stack.push(']');break;
	   case '{':
	    stack.push('}');break;
	   default:
	    break;
	   }	
	if (c == ')' || c == ']' || c =='}') { //遇到右括号出栈
    		if (stack.empty()) {    //如果遇到右括号时栈为空，表示肯定不匹配
     			return false;
   		 }
    		char r = (char) stack.pop();  //出栈一个左括号
    		if(r != c)
    		 return false;
   		}
  	}
  	return stack.empty();
}