今日题目
T20 有效的括号(简单，栈)
题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
标签
栈
解析
直接利用栈进行匹配即可。
python解法
class Solution:def isValid(self, s: str) -> bool:if not s:return Truesize = -1stack = list()for i in s:if i in ['(', '[', '{']:size += 1stack.append(i)else:if size < 0:return Falseif i == ')':if stack[size] == '(':stack.pop()size -= 1else:return Falseif i == ']':if stack[size] == '[':stack.pop()size -= 1else:return Falseif i == '}':if stack[size] == '{':stack.pop()size -= 1else:return Falsereturn len(stack) == 0
C++解法
class Solution
{
public:bool isValid(string s){int len = s.size();stack<char> s1;for (char c : s){if (c == '(' || c == '[' || c == '{'){s1.push(c);}else{if (s1.empty()){return false;}char c1;switch (c){case ')':c1 = '[';break;case ']':c1 = '[';break;case '}':c1 = '{';break;default:c1 = '\0';break;}if (c1 != s1.top()){return false;}s1.pop();}}return s1.empty();}
};