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.

tag: stack, string

5/10/2015 update

a neater approach, with a stack.

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++){
            char c = s[i];
            if(c == '(' || c == '{' || c == '['){
                st.push(c);
            }
            else{
                if(isMatch(st.top(), c)){
                    st.pop();
                }
                else {
                    return false;
                }
            }
        }
        return st.empty();
    }
    bool isMatch(char l, char r){
        char map[][2] = {{'(',')'},{'[',']'},{'{','}'}};
        for(int i = 0; i < 3; i++){
            if(l == map[i][0] && r == map[i][1]){
                return true;
            }
        }
        return false;
    }
};

用一个栈，实现对合法括号的parse。很像编译原理或计算理论中讲到过的自动机。

代码写的很糙，待优化空间很大。

class Solution {
public:
    stack<char> st;
    bool isValid(string s) {
        for(size_t i = 0; i < s.size(); i++){
            char c = s[i];
            if( c == '(' || c == '[' || c == '{'){//start symbol
                st.push(c);
            }
            else{
                if(st.empty()){//s is empty
                    return false;
                }
                else{
                    char lc = st.top();
                    st.pop();
                    switch(lc){
                        case '(':
                            if (c != ')'){
                                return false;
                            }
                            else{
                                break;
                            }
                        case '[':
                            if(c != ']'){
                                return false;
                            }
                            else{
                                break;
                            }
                        case '{':
                            if(c != '}'){
                                return false;
                            }
                            else{
                                break;
                            }
                    }
                }
            }
        }
        if(st.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};