括号匹配问题-----使用栈进行解题
欢迎大家关注我的个人刷题公众号~~~
今天做个简单题,常见的括号是否匹配问题,在入参判断合法性的时候发现一个比较好玩的想不明白的用例,输入空字符串,竟然是true,大家见过这样的吗?
第一把跑的时候,有四个用例没过,发现是"(("这种用例没过,是最后应该判断栈stk是否全部pop出去即是否为空。
本题思路清晰简单,遇到左括号就入栈,否则就判断栈顶是否是对应的对象,是的话就出栈,最后遍历完后,成对的话栈一定是空的,其他情况都是false。
一定要多自己构造些用例,不要让运行的时候判断自己那些场景没想到~~~如果某个考试或者面试系统只能运行给结果,不给你哪个没过~~~~~是不是特别想哭~~~~真的有这样的系统哦~~~~~~
读者们有没有见过遇到过这样的系统呀~~~请留言~~~~下呗~~
20. 有效的括号
难度简单1536
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
-
左括号必须用相同类型的右括号闭合。
-
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
习惯了本地也把要用的数据头文件加进来~
#include <string>
#include <iostream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
class Solution {
public:
bool isValid(string s) {
// 当是奇数的时候一定不能成对匹配左右。
if (s.size() % 2 != 0) {
return false;
}
stack<char> stk;
set<char> setLeft;
setLeft.insert('(');
setLeft.insert('[');
setLeft.insert('{');
for (int i = 0; i < s.size(); i++) {
// 左边类型的时候入栈
if (setLeft.find(s[i]) != setLeft.end()) {
stk.push(s[i]);
continue;
}
// 判断为右边的时候,判断是否栈顶和自己是一对,不是一对直接false.
if (s[i] == ')' && (stk.empty() || stk.top() != '(')) {
return false;
}
if (s[i] == ']' && (stk.empty() || stk.top() != '[')) {
return false;
}
if (s[i] == '}' && (stk.empty() || stk.top() != '{')) {
return false;
}
stk.pop();
}
// 最后判断成对的括号是否全部匹配,匹配的时候此时栈为空的,否则不匹配。
if (!stk.empty()) {
return false;
}
return true;
}
};