Leetcode每日一题 —— 20. 有效的括号

思路

典型的栈应用题，每次遇到右括号时，栈顶应该有相应的左括号。最后栈不能为空。

代码

class Solution {

public:

    bool isValid(string s) {

        // 用栈即可

        stack<char> stk;

        for(char c:s){

            switch(c){

                case ')':

                    if(stk.empty()||stk.top()!='('){

                        return false;

                    }

                    stk.pop();

                    break;

                case '}':

                    if(stk.empty()||stk.top()!='{'){

                        return false;

                    }

                    stk.pop();

                    break;

                case ']':

                    if(stk.empty()||stk.top()!='['){

                        return false;

                    }

                    stk.pop();

                    break;

                default:

                    stk.emplace(c);

            }

        }

        // 注意最后栈不能为空

        return stk.empty();

    }

};