题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

解答

class Solution {
public:
    bool isValid(string s) {
        //本题使用栈来解决
        stack<char> stk;
        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i];
            switch(c)
            {
                case '(':
                case '[':
                case '{':
                    //遇到左括号，就入栈
                    stk.push(c);
                    break;
                case ')':
                case ']':
                case '}':
                    //遇到右括号则，则查看栈顶中的元素是否是与其匹配的左括号
                    if(stk.size() && ((stk.top() == '(' && c == ')')
                        || (stk.top() == '[' && c == ']')
                        || (stk.top() == '{' && c == '}')))
                        {
                            //匹配就出栈
                            stk.pop();
                        }
                        else
                        {
                            //否则，就可以判断不是有效字符
                            return false;
                        }
                    break;
                default:
                break;

            }
        }

        //最后，如果栈中元素个数为0，就为有效字符
        return !stk.size();
    }
};