20. Valid Parentheses

问题描述：
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

分析：
这道题判断括号是否是合法的，成对出现的。还是比较简单的，需要用到栈，遍历字符串，遇到左括号就入栈，遇到右括号就出栈，判断出栈的字符和当前的字符是否是一对。出栈之前要先判断栈是否为空，如果为空，返回false。遍历完字符串之后，如果栈为空，说明所有的括号都匹配成功，返回true，否则，返回false。代码如下：

  public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(isLeft(c)) stack.push(c);
            else{
                if(stack.empty()) return false;
                else{
                    char p = stack.pop();
                    if(!isCouple(p,c)) return false;
                }
            }
        }
        return stack.empty(); 
    }
    //判断是否是左括号
    private boolean isLeft(char c){
        if(c=='(' || c=='[' || c=='{') return true;
        else return false;
    }
    //判断是否是一对
    private boolean isCouple(char a, char b){
        switch(a){
            case '(':
                if(b == ')') return true;
                else return false;
            case '[':
                if(b == ']') return true;
                else return false;
            case '{':
                if(b == '}') return true;
                else return false;
            default:
                return false;
        }
    }