这篇文章主要讲解了“C++怎么实现验证括号”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++怎么实现验证括号”吧!
Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。这里需要用一个栈,开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回 false,如不为空,则取出栈顶元素,若为对应的左半边括号,则继续循环,反之返回 false,代码如下:
方法一:
class Solution {
public:
bool isValid(string s) {
stack<char> parentheses;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == "(" || s[i] == "[" || s[i] == "{") parentheses.push(s[i]);
else {
if (parentheses.empty()) return false;
if (s[i] == ")" && parentheses.top() != "(") return false;
if (s[i] == "]" && parentheses.top() != "[") return false;
if (s[i] == "}" && parentheses.top() != "{") return false;
parentheses.pop();
}
}
return parentheses.empty();
}
};
方法二:
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{")", "("},
{"]", "["},
{"}", "{"}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
感谢各位的阅读,以上就是“C++怎么实现验证括号”的内容了,经过本文的学习后,相信大家对C++怎么实现验证括号这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/3335309/blog/4589117