數據結構之棧的應用----C程序的括號配對檢查

已經對棧的應用有了一定的了解了，並且感覺到數據結構實在是很強大，它幾乎可以解決我們生活中的大部分問題。

關於棧的基本常識，這裡不做過多的解釋，總之，其核心就是先進後出（FILO）

聯想到這種模式我們就可以很容易的知道，棧可以有如下幾種應用：

1、進制之間的轉換

2、C程序的括號配對檢查

3、迷宮求解問題

4、算術表達式求值

5、遞歸函數

......

這裡，我將以一個括號配對檢查的程序為例，講述棧的應用。。。（之一）

起初看到這個題目是在K&R的書上看見的，當時看這個題時，簡直是找不到東南西北，就算看了答案也是模稜兩可的，

現在時隔半年，當我學到棧的時候，我才對這個程序有了一個新的角度去理解，感覺著用棧去解決這個程序在思想上

很容易理解，但是效率上還不清楚，畢竟能力還沒達到可以提高程序運行效率的地步。

『首先，我們得了解實現這個程序的基本思想：

1、我們從一個C程序文本中查找括號（包括{},(),[],<>），當我們檢測到其中之一時，就將它push到棧中，如果棧裡的

top元素和它配對了（如："{和}"，"(和)"，"[和]","<和>"。"}和{"不能算），就把它和top元素依次pop出來，當文本檢查完

，到了EOF時，如果棧為空，則說明括號配對了，反之，則說明此C程序括號的配對有問題

2、然後，我們還需要解決一個問題，要是有雙引號和注釋符怎麼辦？很簡單，我們在檢查文本時，把它們當作特殊情

況處理，如果遇到了雙引號和注釋符，並且它們都配對了，則把它們之間的所有內容忽略掉就OK了』

有了上述思想，我想這個程序應該就很容易實現了，我把它分為了如下幾個步驟：

1、實現一個C程序文本的獲取功能，可以通過實現獲取一行字符的功能來實現獲取一段文本的功能

（1）我們可以寫一個名叫getline的函數，它的功能是從用戶的輸入中提取一行存入到一個字符串（char *line）中，並

以'\n'+'\0'為每行結尾，返回這一行的字符數，不能將'\n'+'\0'計入其中；

（2）有了getline這個函數，我們對實現一段文本的提取就有了基礎了，我們寫這麼一個名叫gettext的函數，只需每獲取

一行之後就將這一行的首地址存入到一個字符串指針的形參中就可以了，形參為：char **text,int i一開始我的想法很簡單，

在gettext函數裡定義一個line的數組（char line[MAXLINE]），然後直接getline，然後text[i++] = line;就OK了，但是問題就

在這裡產生了，如果每一次的line都通過這個賦值語句傳給*text的每一個元素*text[0],*text[1]...*text[n]，那麼text的每一行

都將與最新的line相關聯，畢竟這是指針賦值給指針啊！！！而且，當這個gettext函數銷毀時，line數組也隨之銷毀，text

裡的每一行將會成為野指針所隨機指向的一塊內存，這是一個相當大的問題啊！！！解決這個問題的辦法就是為每一line

申請一塊動態內存空間，當然，必須得把line定義為指針了。

這個功能實現的關鍵幾步：

/** 為line指針申請動態內存，防止被銷毀**/

1. char *line = (char *)malloc(sizeof(char)*MAXLINE);  

/** 一個獲取text的循環**/

1. //malloc a string line   
2. while(1)  
3. {  
4.     lineLen = getline(line,MAXLINE);  
5.     text[i] = line;  
6.     ++i;  
7.   
8.     if(YES == hasEOF(line))  
9.         break;  
10.   
11.     line = (char *)malloc(sizeof(char)*MAXLINE);  
12. }