题目

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

思路

此处是栈的应用,只需要建立一个栈,此处使用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]将整体封装可以自由定义符号。