目錄
目錄
題目描述
題目分析解析
解決代碼
寫題感悟:
題目描述
還有實例
題目分析解析
對于這個題目,我們首先有效字符串需要滿足什么,第一個左右括號使用相同類型的括號,這好理解,無非就是小括號和小括號大括號和大括號一起匹配。其次第二個就是左括號必須以正確順序來匹配,注意了是順序,大家以為就是左括號(小括號)遇到左括號(中括號)然后遇到了右括號(小括號)和右括號(中括號),然而恰恰相反,而是小括號(左)、中括號(右)和中括號(右)小括號(右)相依匹配(大致就是遇到第一個右括號時,然后與自己最近的左括號進行匹配,假設匹配成功消除,第二個右括號繼續匹配最近的括號)。最后就是第三個和我們將的第一個差不多,就是和對應的左括號匹配,但是這里主要是限制只有右括號的情況。
接下來就是如何解決問題了。
這里我們根據第二個要求,可以知道當遇到右括號時,需要找到與之最近的左括號匹配,通過這個我們就能想到,當遇到右括號時把后進的左括號與之對比看是否滿足相同類型括號。這個后進先出就和我們學過的數據結構棧有關系,所以我們這里需要數據結構棧來寫。將遇到的左括號存入棧中,直到遇到右括號(這里還得考慮是否右括號),判斷是否匹配成功,只要有一個匹配失敗,就說明這個字符串不符合有效字符,以上都符合后,最后判斷棧是否還有左括號,如果沒有則符號題目要求。
解決代碼
//棧結構
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
//初始化
void StackInit(ST* Stack)
{Stack->arr = NULL;Stack->capacity = Stack->top = 0;
}//入棧
void StackPush(ST* Stack, STDataType x)
{assert(Stack);//空間不夠if (Stack->capacity == Stack->top){//擴容int newcapacity = Stack->capacity == 0 ? 4 : 2 * Stack->capacity;STDataType* tmp = (STDataType*)realloc(Stack->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc");exit(1);}Stack->arr = tmp;Stack->capacity = newcapacity;}//空間夠Stack->arr[Stack->top++] = x;
}//判斷
bool StackEmpty(ST* Stack)
{assert(Stack);return Stack->arr==NULL;
}//出棧
void StackPop(ST* Stack)
{assert(!StackEmpty(Stack));--Stack->top;
}//獲取棧中元素
STDataType StackTop(ST* Stack)
{assert(!StackEmpty(Stack));return Stack->arr[Stack->top - 1];
}//獲取棧中元素個數
int StackSize(ST* Stack)
{assert(!StackEmpty(Stack));return Stack->top;
}//銷毀棧
void StackDestory(ST* Stack)
{if (Stack->arr)free(Stack->arr);Stack->arr = NULL;Stack->capacity = Stack->top = 0;
}bool isValid(char* s) {ST st;
StackInit(&st);
char* cur = s;
while (*cur != '\0')
{//遇到左括號存入棧if (*cur == '('|| *cur == '['|| *cur == '{'){StackPush(&st, *cur);}//遇到右括號取棧頂元素進行對比else{//內部棧為空時(只有右括號時)if(st.top == 0){return false; }char top = StackTop(&st);if (*cur == ')' && top != '('|| *cur == ']' && top != '['|| *cur == '}' && top != '{'){StackDestory(&st);return false;}StackPop(&st);}cur++;
}
if (!StackSize(&st))
{return true;
}
else
{return false;
}
}
寫題感悟
????????這道題對于初學者的我很難想到盡然會用到數據結構棧,這說明數據結構在刷題過程中發揮著不可磨滅的作用。因此我覺得思路和知識都很重要,當然知識是的重要占大頭,沒有知識就沒有這個思路,就算給你一個思路,也很難實現。我覺得在前期的刷題過程需要刻意取練習,到后面就需要綜合去刷,利用自己學到的知識去解決問題,這個題目告訴我如果遇到先進后出或者后進需要先出類似的題目,首先可以考慮棧。