【C/C++|DataStructure】有效的括号

共 3174字,需浏览 7分钟

 ·

2021-04-13 23:22


本文章适合有一定C/C++基础,对数据结构感兴趣的同学。

当然,同时我也给出了Python版本的解答。本文选自leetcode第20题:有效的括号

如果你觉得C语言很难,为什么不试试Python呐?



20:有效的括号

难度:简单


给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。


有效字符串需满足:


左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。


总体思路:

用栈实现括号匹配:

        依次扫描所有字符,遇到左括号入栈,遇到右括号则弹出栈顶元素检

        查是否匹配。

        匹配失败情况:

        ①左括号单身②右括号单身③左右括号不匹配


先来总体看一下两种编程语言的差距,来个直观的感受,其中C++用了代码60行左右,Python20行左右:


C++版

#define MaxSize 10000  //定义栈中最大元素个数
typedef struct{ char data[MaxSize]; //ElemType元素类型,例如int int 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; //指针+1 S.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; //指针-1 return 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 False topElem = S_list.pop() if (i == ')' and topElem != '('): return False if (i == ']' and topElem != '['): return False if (i == '}' and topElem != '{'): return False if S_list == []: return True else: return False



如果你觉得C语言很难,为什么不试试Python呐?


猜你喜欢

                                

                                           



浏览 29
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报