【C/C++|DataStructure】有效的括号
Python小灶
共 3174字，需浏览 7分钟
·
2021-04-13 23:22
本文章适合有一定C/C++基础，对数据结构感兴趣的同学。
当然，同时我也给出了Python版本的解答。本文选自leetcode第20题：有效的括号
如果你觉得C语言很难，为什么不试试Python呐？
20：有效的括号
难度：简单
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
总体思路：
用栈实现括号匹配：
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检
查是否匹配。
匹配失败情况：
①左括号单身②右括号单身③左右括号不匹配
先来总体看一下两种编程语言的差距，来个直观的感受，其中C++用了代码60行左右，Python20行左右：
C++版
typedef struct{char data[MaxSize]; //ElemType元素类型，例如intint top; //定义栈顶指针}SqStack;//初始化栈void InitStack(SqStack &S){S.top = -1; //从-1开始是因为S.top指向元素下标，当第一个元素进来，top+1正好对应下标0}//新元素入栈bool push(SqStack &S, char x){if(S.top == MaxSize - 1){ //栈满return false;}else{S.top = S.top + 1; //指针+1S.data[S.top] = x; //新元素入栈return true;}}//栈的判空bool StackEmpty(SqStack S){if (S.top == -1){return true; //栈空}else{return false; //不空}}//出栈bool Pop(SqStack &S, char &x){if(S.top == - 1){ //空栈return false;}else{x = S.data[S.top]; //获取要出栈的元素S.top = S.top - 1; //指针-1return true;}}class Solution {public:bool isValid(string s) {SqStack S;InitStack(S);int len = s.size();for(int i=0; i<len; i++){if(s[i]=='(' || s[i]=='[' || s[i]=='{'){push(S, s[i]);}else{if (StackEmpty(S))return false;char topElem;Pop(S, topElem);if (s[i] == ')' && topElem != '(')return false;if (s[i] == ']' && topElem != '[')return false;if (s[i] == '}' && topElem != '{')return false;}}return StackEmpty(S);}};
python版
class Solution:def isValid(self, s: str) -> bool:"""用栈实现括号匹配：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。匹配失败情况：①左括号单身②右括号单身③左右括号不匹配"""S_list = []for i in s:if (i == '(' or i == '[' or i == '{'):S_list.append(i)else:if S_list == []:return FalsetopElem = S_list.pop()if (i == ')' and topElem != '('):return Falseif (i == ']' and topElem != '['):return Falseif (i == '}' and topElem != '{'):return Falseif S_list == []:return Trueelse:return False
如果你觉得C语言很难，为什么不试试Python呐？
猜你喜欢
评论