[C++][栈的应用]括号序列

题目

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

思路

此处是栈的应用，只需要建立一个栈，此处使用vector容器作为栈的容器。

1. 建立一个栈；
2. 遍历string，遇到左括号入栈，遇到右括号则与栈顶元素比较;
3. 如果栈顶元素与遍历到的元素不匹配，false;
4. 遍历完成，如果栈内还有元素，false;
5. 其他情况true。

当然C++提供一个直接的栈，可以直接使用stack容器替代。

代码

vector作为栈容器；

stack容器也可以使用，替换相关方法既可。

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        /** 遍历括号

         */
        // 每个括号的标识
        const char b1 = '{', b2 = '}',
            m1 = '[', m2 = ']',
            s1 = '(', s2 = ')';

        // 存储目前括号的容器
        vector<char> cvec;

        // 遍历字符串
        for (auto c : s) {
            switch (c) {
            case m1:
            case b1:
            case s1:
                cvec.push_back(c);
                break;
            case m2:
                // 防止访问越界
                if (0 != cvec.size() && *(cvec.end() - 1) == m1) {
                    cvec.pop_back();
                } else {
                    return false;
                }
                break;
            case b2:
                if (0 != cvec.size() && *(cvec.end() - 1) == b1) {
                    cvec.pop_back();
                } else {
                    return false;
                }
                break;
            case s2:
                if (0 != cvec.size() && *(cvec.end() - 1) == s1) {
                    cvec.pop_back();
                } else {
                    return false;
                }
                break;
                // 若非符号，则下一个
            default:
                continue;
            }
        }

        // 容器最后无内容，匹配成功
        if (0 == cvec.size()) {
            return true;
        }

        // 默认返回false
        return false;

    }
};

其他

本处考虑了其中混杂了其他符号或者字符的情况，有default语句。

若需要添加其他情况，比如匹配更多符号，代码这么写会显得冗杂，可以尝试封装case语句部分的判断成私有方法。

[TODO]将整体封装可以自由定义符号。