题目
给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。
思路
此处是栈的应用,只需要建立一个栈,此处使用vector
容器作为栈的容器。
- 建立一个栈;
- 遍历
string
,遇到左括号入栈,遇到右括号则与栈顶元素比较; - 如果栈顶元素与遍历到的元素不匹配,
false
; - 遍历完成,如果栈内还有元素,
false
; - 其他情况
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]将整体封装可以自由定义符号。