【C/C++|DataStructure】有效的括號
本文章適合有一定C/C++基礎(chǔ)，對數(shù)據(jù)結(jié)構(gòu)感興趣的同學(xué)。
當(dāng)然，同時(shí)我也給出了Python版本的解答。本文選自leetcode第20題：有效的括號
如果你覺得C語言很難，為什么不試試Python吶？
20：有效的括號
難度：簡單
給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
總體思路：
用棧實(shí)現(xiàn)括號匹配：
依次掃描所有字符，遇到左括號入棧，遇到右括號則彈出棧頂元素檢
查是否匹配。
匹配失敗情況：
①左括號單身②右括號單身③左右括號不匹配
先來總體看一下兩種編程語言的差距，來個(gè)直觀的感受，其中C++用了代碼60行左右，Python20行左右：
C++版
typedef struct{char data[MaxSize]; //ElemType元素類型，例如intint top; //定義棧頂指針}SqStack;//初始化棧void InitStack(SqStack &S){S.top = -1; //從-1開始是因?yàn)镾.top指向元素下標(biāo)，當(dāng)?shù)谝粋€(gè)元素進(jìn)來，top+1正好對應(yīng)下標(biāo)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; //?？?/span>}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:"""用棧實(shí)現(xiàn)括號匹配：依次掃描所有字符，遇到左括號入棧，遇到右括號則彈出棧頂元素檢查是否匹配。匹配失敗情況：①左括號單身②右括號單身③左右括號不匹配"""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吶？
猜你喜歡
評論
圖片
表情