• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜歡《數據結構》部分筆記的小伙伴可以訂閱專欄，今后還會不斷更新。🧑?💻
此外，《程序員必備技能》專欄和《程序員必備工具》專欄（該專欄暫未開設）日后會逐步更新，感興趣的小伙伴可以點一下訂閱、收藏、關注！🚀
謝謝大家！🙏

括號示例

void test(){int a[10][10];int x = 10*(20*(1+1)-(3-2));printf("加油！奧里給！");
}

流程應該為：

• 遇到左括號就入棧
• 遇到右括號，就“消耗”一個左括號
• 處理完所有括號后，棧非空——左括號單身
• 因此寫代碼的時候，掃描完所有的括號后，還要檢查是否棧空
• 如果棧非空，則匹配失敗

算法實現

#define MaxSize 10
typedef struct{char data[MaxSize];int top;
}SqStack;/*
* 考試中可以直接使用棧的這些基本操作
* 但是建議要寫上簡短的說明接口分別是什么
*///初始化棧
void InitStack(SqStack &S)
//判斷棧是否為空
bool StackEmpty(SqStack S)
//新元素入棧
bool Push(SqStack &S, char x)
//棧頂元素出棧，用x返回
bool Pop(SqStack &S, char &x)bool bracketCheck(char str[], int length){SqStack S;                  //聲明一個棧InitStack(S);               //初始化一個棧for(int i=0; i>length; i++){if(str[i] == '(' || str[i] == ')' || str[i] == '{'){Push(S, str[i]);    //掃描到左括號，入棧}else{if(StackEmpty(S))   //掃描到右括號，且當前棧空return false;   //匹配失敗char topElem;Pop(S, topElem);    //棧頂元素出棧if(str[i] == ')' && topElem != '(')return false;if(str[i] == ']' && topElem != '[')return false;if(str[i] == '}' && topElem != '{')return false;}}return StackEmpty(S);   //檢索完所有括號后，棧空說明匹配成功
}

需要注意的是，當前定義的最大長度是10，如果長度不夠了怎么辦？
答：可以用鏈棧的方式來實現，不過在考試中用順序棧來實現更方便，所以用順序棧就可以了

---

練習：去掉代碼中的基本操作，把相對應的邏輯換成對數組和top指針直接的判斷和操作，動手實現完整代碼！
答案：

• 先將基本操作替換一下

//首先，初始化棧
//將棧的top指針初始化為 -1，表示棧為空
S.top = -1;//判斷棧是否為空
//也就是判斷top是否為 -1，如果是，表示棧空
if(S.top == -1)//新元素入棧，將元素放在top指針所指位置的下一位，并將top指針 +1
if(S.top < MaxSize - 1){S.data[++S.top] = str[i];
}else{return false;
}//棧頂元素出棧，獲取top指針所指位置的元素，并將top指針 -1
if(S.top != -1){topElem = S.data[S.top--];
}else{return false;
}

• 最終完整代碼

#include <stdbool.h>
#include <stdio.h>#define MaxSize 10typedef struct{char data[MaxSize];int top;
}SqStack;bool bracketCheck(char str[], int length){SqStack S;    //聲明一個棧S.top = -1;   //初始化棧for(int i = 0; i < length; i++){if(str[i] == '(' || str[i] == '[' || str[i] == '{'){if(S.top < MaxSize - 1){S.data[++S.top] = str[i];  //掃描到左括號，入棧}else{return false;  //棧滿，匹配失敗}}else if(str[i] == ')' || str[i] == ']' || str[i] == '}'){if(S.top == -1)    //掃描到右括號，且當前棧空return false;  //匹配失敗char topElem;if(S.top != -1){topElem = S.data[S.top--];  //棧頂元素出棧}else{return false;  //棧空，匹配失敗}if((str[i] == ')' && topElem != '(') ||(str[i] == ']' && topElem != '[') ||(str[i] == '}' && topElem != '{'))return false;  //匹配失敗}}return S.top == -1;  //檢索完所有括號后，棧空說明匹配成功
}int main(){char str[] = "{[()]}";int length = sizeof(str) / sizeof(str[0]) - 1;bool result = bracketCheck(str, length);if(result)printf("括號都是成對的\n");elseprintf("括號不是成對的\n");return 0;
}

以上代碼的問題解答：

1. 為什么用S.top == MaxSize - 1這個條件來判斷是否棧滿？為什么MaxSize要-1 ？
   • 在使用數組實現棧的情況下，我們需要知道數組的最大容量。假設數組的最大長度為 MaxSize，那么數組的索引范圍是從 0 到 MaxSize - 1。也就是說，數組中最后一個位置的索引是 MaxSize - 1。
   • S.top：棧頂指針，指向當前棧頂元素的位置；MaxSize - 1：數組的最大索引。
   • 如果 S.top 正好等于 MaxSize - 1，說明棧頂已經在數組的最后一個位置，因此棧中已經沒有空余的空間可以容納更多的元素，棧已經滿了。
2. S.data[++S.top] = str[i]; // 入棧時，是先將指針+1，還是先壓入數據？
   • 在這條語句中，++S.top 是一個前置自增操作。這意味著：
     • S.top 會先增加 1，然后新值會被用作索引來存放新元素 str[i]
     • 也就是說，S.top會先增加一，然后指向下一個位置，然后在指向的這個位置里面插入元素str[i]
3. str[i]是什么意思？其中的i又是什么意思？
   • str：是一個字符數組（字符串），它包含了需要被檢查的括號字符。
   • i：是一個整數，作為循環變量，表示當前在數組 str 中的索引。循環遍歷 str 數組中的每一個字符，通過 str[i] 來訪問 str 數組在第 i 個位置的字符
4. 在這個for循環中，只要有任意一次匹配失敗，就會中斷循環，并且返回false