423.Valid Parentheses

1.Description(Medium)

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

Example

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

2.Code

括号匹配问题用stack解再合适不过。括号组合是否有效，主要看右括号。右括号的数量必须要等于相应的左括号。而左右括号之间也必须是有效的括号组合。

1. 当前括号是左括号时，压入stack。

2. 当前括号是右括号时，stack.top()如果不是对应的左括号，则为无效组合。否则，pop掉stack里的左括号。

3. 所有字符都判断处理过后，stack应为空，否则则无效。

public boolean isValidParentheses(String s) {
        if(s==null || s.length()==0){
            return true;
        }
        char[] str=s.toCharArray();
        Stack<Character> stack=new Stack<Character>();
        for(int i=0;i<str.length;i++){
            char current=str[i];
            if(current=='(' || current=='{' || current=='['){
                stack.push(current);
            }
            if(current==')'){
                if(stack.isEmpty() || stack.peek()!='(' ){
                    return false;
                }else{
                    stack.pop();
                }
            }
            if(current=='}'){
                if(stack.isEmpty() || stack.peek()!='{' ){
                    return false;
                }else{
                    stack.pop();
                }
            }
            if(current==']'){
                if(stack.isEmpty() || stack.peek()!='[' ){
                    return false;
                }else{
                    stack.pop();
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }

以上写法可以把判断封装成函数，可读性更高。