1.括號(hào)匹配

void matching(char str[])
{//創(chuàng)建空棧LinkStack S;S = NULL;int k;int flag = 1;char e;for (k = 0; str[k] != '\0'; k++){if (str[k] != '(' && str[k] != ')' && str[k] != '[' && str[k] != ']' && str[k] != '{' && str[k] != '}'){//非括號(hào)處理continue;}switch (str[k])//對(duì)括號(hào)進(jìn)行匹配處理{case '(':case '{':case '['://遇到左括號(hào)進(jìn)棧PushLinkStack(&S, str[k]);break;case ')'://遇到右圓括號(hào)if (S != NULL){GetTopStack(S, &e);if (e == '('){PopLinkStack(&S, &e);//棧頂是左圓括號(hào)，匹配成功}else{flag = 0;//棧頂不是左圓括號(hào)，匹配失敗}}else{flag = 0;//棧空，匹配失敗}break;case ']'://遇到右方括號(hào)if (S != NULL){GetTopStack(S, &e);if (e == '['){PopLinkStack(&S, &e);//棧頂是左方括號(hào)，匹配成功}else{flag = 0;//棧頂不是左方括號(hào)，匹配失敗}}else{flag = 0;//?？?#xff0c;匹配失敗}break;case '}'://遇右花括號(hào)if (S != NULL){GetTopStack(S, &e);if (e == '}'){PopLinkStack(&S, &e);//棧頂是左右花括號(hào)，匹配成功}else{flag = 0;//棧頂不是左右花括號(hào)，匹配失敗}}else{flag = 0;//?？?#xff0c;匹配失敗}break;                      }//switch}//forif (flag == 1 && S == NULL){printf("括號(hào)匹配!\n");}else{printf("括號(hào)不匹配！\n");}
}

2.表達(dá)式求值

C語(yǔ)言有著豐富的表示式，那么C的編譯器是如何處理表達(dá)式的呢？

2.1.算術(shù)表示式的形式

數(shù)學(xué)上的算法表達(dá)式通常包括操作數(shù)和運(yùn)算符。

• 操作數(shù)：簡(jiǎn)單變量或表達(dá)式，用s1,s2表示。
• 運(yùn)算符：+、-，*，/，（，），用op表示。

通常的算術(shù)表達(dá)形式即為數(shù)學(xué)表達(dá)式形式，如3*(5-2)+7。由于運(yùn)算符的優(yōu)先級(jí)，因此求值不一定能夠按照從左向右的順序執(zhí)行。如果能將算術(shù)表示式轉(zhuǎn)成易于從左向右的順序執(zhí)行，即可大大提高計(jì)算機(jī)的執(zhí)行效率。
算術(shù)表達(dá)式除了數(shù)學(xué)上的表達(dá)形式外，還有如下三種表達(dá)形式。
（1）中綴表達(dá)式（運(yùn)算符位于兩個(gè)操作數(shù)之間）：s1 op s2
（2）前綴表達(dá)式（運(yùn)算符位于兩個(gè)操作數(shù)之前）: op s1 s2
（3）后綴表達(dá)式（運(yùn)算符位于兩個(gè)操作數(shù)之后）: s1 s2 op

以算術(shù)表達(dá)式 3*(5-2)+7為例，下面給出算術(shù)表達(dá)形式的步驟。依次處理算術(shù)表達(dá)式中級(jí)別較低的運(yùn)算符，為了從形式上明確運(yùn)算符的兩個(gè)操作對(duì)象，約定當(dāng)操作對(duì)象是表達(dá)式時(shí)，用一對(duì)花括號(hào)括起來(lái)，結(jié)果如下。

• 中綴表達(dá)式的處理順序。
  ①處理‘+’：{3 * (5-2)} + 7; ②處理‘ * ’：3 * {5-2} +7; ③處理‘-’：3 * 5-2+7
• 前綴表達(dá)式的處理順序。
  ①處理‘+’：+{3 * （5-2）}7；②處理‘ * ’：+ * 3{（5-2）}7；③處理‘-’：+ * 3-527
• 后綴表達(dá)式的處理順序。
  ①處理‘+’：{3 * （5-2）}7+；②處理‘ * ’：3{（5-2）} * 7+；③處理‘-’：352 - * 7+

不難看出：三種表達(dá)式的操作數(shù)順序相同，但運(yùn)算符順序不一。其中，中綴表達(dá)式丟失了算術(shù)表達(dá)式中的括號(hào)信息，致使運(yùn)算符的運(yùn)算順序不能確定，計(jì)算會(huì)出現(xiàn)二義性；前綴表達(dá)式的運(yùn)算規(guī)則是連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小的表達(dá)式，由于運(yùn)算符的順序與計(jì)算機(jī)算順序不一致，因此需要多次掃描前綴式，才能得到表達(dá)式的計(jì)算，效率低；后綴表達(dá)式中的運(yùn)算規(guī)則是連續(xù)出現(xiàn)兩個(gè)操作數(shù)和在它們之后緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小的表達(dá)式，由于運(yùn)算符的順序與計(jì)算機(jī)順序一致，因此只需一次掃描后綴式，即可完成表達(dá)式的計(jì)算，效率高。

2.2.后綴表達(dá)式求值

求值過(guò)程：后綴表達(dá)式是一個(gè)字符串，為了方便處理，以‘#’結(jié)束。用一個(gè)棧（假定數(shù)據(jù)元素類型為整型）來(lái)存放操作數(shù)和中間計(jì)算結(jié)果。對(duì)后綴表達(dá)式從左向右依次掃描，若是操作數(shù)，則將字符轉(zhuǎn)換成整數(shù)進(jìn)棧；若是運(yùn)算符，則連續(xù)出棧兩次，第一出棧的元素是第二個(gè)操作數(shù)，第二次出棧的元素是第一個(gè)操作數(shù)，根據(jù)當(dāng)前的運(yùn)算符做相應(yīng)的運(yùn)算，并將結(jié)果進(jìn)棧，直到‘#’為止。此時(shí)棧中只剩下一個(gè)元素，即最后的結(jié)果，出棧即刻。

int suffix_value(char a[])//a指向后綴表達(dá)式
{int i = 0, x1,x2, result;LinkStack S=NULL;while (a[i]!='#'){switch (a[i]){case '+':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 + x2);break;case '-':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 - x2);break;case '*':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 * x2);break;case '/':PopLinkStack(&S, &x2);PopLinkStack(&S, &x1);PushLinkStack(&S, x1 / x2);break;default:PushLinkStack(&S, a[i] - '0');}//end_switchi++;//訪問(wèn)下一個(gè)}PopLinkStack(&S, &result);return result;
}//suffix_value

2.3.將算術(shù)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

為了方便將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，不妨在算術(shù)表達(dá)式的末尾增加一個(gè)字符‘#’，在算術(shù)運(yùn)算符中增加一個(gè)‘#’運(yùn)算符。
用一個(gè)字符棧來(lái)存放運(yùn)算符。先用‘#’初始化字符棧，再對(duì)表達(dá)式字符串中的每一個(gè)字符從左到右依次做一下處理。
（1）如果當(dāng)前字符是操作數(shù)，則將其存放到后綴表達(dá)式中數(shù)組中。
（2）如果當(dāng)前字符是運(yùn)算符，則考慮它是否進(jìn)棧。
設(shè)當(dāng)前運(yùn)算符為op，則
（1）當(dāng)op == ‘(’ 時(shí)，op直接進(jìn)棧。
（2）當(dāng)op == ‘)’ 時(shí)，棧頂運(yùn)算符依次出棧，并依次將其按順序存放到后綴表達(dá)式數(shù)組，直到遇到’)‘為止。注意：’('只是出棧，不存放到后綴表達(dá)式數(shù)組。
（3）當(dāng)op的優(yōu)先級(jí)高于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，op進(jìn)棧；否則，棧頂?shù)倪\(yùn)算符依次出棧，存放到后綴表達(dá)式數(shù)組中，直到棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)低于op，op進(jìn)棧。
（4）當(dāng)op == ‘#’ ,棧頂運(yùn)算符依次出棧，存放到后綴表達(dá)式數(shù)組，直到棧頂運(yùn)算符為‘#’，算法結(jié)束。
設(shè)運(yùn)算符的優(yōu)先級(jí)為#，（，+或-，*或/，從左到右由低到高。
判斷優(yōu)先級(jí)的算法

int prior(char a)
{if (a == '*' || a == '/'){return 4;}else if (a == '-' || a == '+'){return 3;}else if (a == '('){return 2;}else if(a=='#'){return 1;}return 0;
}

將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的算法如下：
【算法】

void Transformation(char a[], char suff[])
{//a指向算術(shù)表達(dá)式，以'#'結(jié)束，棧用于存放運(yùn)算符//將a指向的算術(shù)表達(dá)式轉(zhuǎn)換成由suff指向的后綴表達(dá)式int i = 0;int k = 0;int n;char ch;LinkStack s;s = NULL;PushLinkStack(&s, '#');n = strlen(a);//在表達(dá)式的末尾添加一個(gè)#a[n] ='#';a[n + 1] = '\0';while (a[i] != '\0'){if (a[i] >= '0' && a[i] <= '9'){//是操作數(shù)，直接存入后綴表達(dá)式suff[k++] = a[i];}//是運(yùn)算符else{switch (a[i]){case '(':PushLinkStack(&s, a[i]);//進(jìn)棧break;case ')'://將左圓括號(hào)之上的運(yùn)算符依次出棧并發(fā)送到后綴表達(dá)式，左圓括號(hào)只是出棧PopLinkStack(&s, &ch);while (ch != '('){suff[k++] = ch;PopLinkStack(&s, &ch);}break;/*比較表達(dá)式當(dāng)前的運(yùn)算符a[i]和棧頂運(yùn)算符的ch的優(yōu)先級(jí)，如果a[i]高于ch，a[i]進(jìn)棧；反之，棧內(nèi)高于a[i]的運(yùn)算符依次出棧并發(fā)往后綴表達(dá)式直到棧頂運(yùn)算符優(yōu)先級(jí)低，在將a[i]進(jìn)棧*/default:GetTopStack(s, &ch);while (prior(ch) >= prior(a[i])){suff[k++] = ch;GetTopStack(s, &ch);}if (a[i] != '#'){PushLinkStack(&s, a[i]);}}//end_switch}//end_elsei++;}//end_whilesuff[k] = '\0';//保證suff存放的是字符串
}//Transformation

以上算法僅適用用于操作數(shù)是個(gè)位數(shù)。要計(jì)算任意實(shí)數(shù)，需要解決如下問(wèn)題。
（1）后綴表達(dá)式中的操作數(shù)與操作數(shù)之間如何隔開(kāi)。
（2）操作數(shù)棧的類型是什么？
（3）如何將一個(gè)數(shù)字串轉(zhuǎn)換為一個(gè)實(shí)數(shù)？
（4）操作數(shù)為負(fù)數(shù)的時(shí)，如何處理？
例如，算術(shù)表達(dá)式為-3+（-15.7+9）* 4.25 + 7/8.2
（1）先處理負(fù)數(shù)的情況。
原則：第一個(gè)字符為‘-’時(shí)，前面加0；‘("之后是’-‘，在’('之后加0。
（2）在操作數(shù)與操作數(shù)之間加空格。

2.4.算術(shù)表達(dá)式直接求值

算法的主要步驟如下。
（1）創(chuàng)建兩個(gè)棧，一個(gè)是運(yùn)算符棧（初始化時(shí)，將’#'進(jìn)棧），另一個(gè)是操作數(shù)中間結(jié)果棧。
（2）對(duì)算術(shù)表達(dá)式從左向右的依次掃描。
①如果算數(shù)表達(dá)式的當(dāng)前字符是操作數(shù)，則將算術(shù)表達(dá)式當(dāng)前的字符轉(zhuǎn)換成整數(shù)進(jìn)操作數(shù)棧。
②如果算術(shù)表達(dá)式的當(dāng)前字符是運(yùn)算符，則將運(yùn)算符棧的棧頂運(yùn)算符進(jìn)行比較。

• 如果算術(shù)表達(dá)式的當(dāng)前運(yùn)算符優(yōu)先級(jí)低于棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)，則棧頂?shù)倪\(yùn)算符出棧，從操作數(shù)棧連續(xù)彈出兩個(gè)操作數(shù)，先出的操作數(shù)第二運(yùn)算對(duì)象，后出的操作數(shù)是第一個(gè)運(yùn)算對(duì)象，對(duì)兩個(gè)操作數(shù)做出棧運(yùn)算符對(duì)應(yīng)的操作，并將計(jì)算結(jié)果結(jié)果進(jìn)操作數(shù)棧，直至棧頂運(yùn)算符的優(yōu)先級(jí)低于算術(shù)表達(dá)式的當(dāng)前運(yùn)算符的優(yōu)先級(jí)為止，再將算術(shù)表達(dá)式的當(dāng)前運(yùn)算符進(jìn)算符棧。
• 如果算術(shù)表達(dá)式的當(dāng)前運(yùn)算符優(yōu)先級(jí)高于棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)，則將算術(shù)表達(dá)式的當(dāng)前運(yùn)算符進(jìn)運(yùn)算符棧。

（3）如果算術(shù)表達(dá)式的當(dāng)前運(yùn)算符是’#‘，則依次彈出運(yùn)算符棧的運(yùn)算符，同時(shí)從操作數(shù)連續(xù)彈出兩個(gè)操作數(shù)做相應(yīng)的操作，并將計(jì)算結(jié)果進(jìn)操作數(shù)棧，直至棧頂?shù)倪\(yùn)算符為’#',算法結(jié)束。

3.棧與遞歸

3.1.遞歸算法

遞歸是計(jì)算機(jī)數(shù)值計(jì)算中的一個(gè)中要算法，它可以將復(fù)雜的運(yùn)算轉(zhuǎn)化為若干重復(fù)的簡(jiǎn)單運(yùn)算，充分發(fā)揮計(jì)算機(jī)重復(fù)處理的特點(diǎn)。把遞歸算法推廣為調(diào)用自身的方法稱為遞歸算法。

遞歸實(shí)質(zhì)是將一個(gè)不好或不能直接求解的“大問(wèn)題”轉(zhuǎn)化為一個(gè)或幾個(gè)“小問(wèn)題”來(lái)解決，這些小問(wèn)題可以繼續(xù)分解成更小的問(wèn)題，直至小問(wèn)題可以直接求解。下面分別介紹這兩種常用的遞歸設(shè)計(jì)。

• 遞歸設(shè)計(jì)方法一
  通過(guò)將問(wèn)題簡(jiǎn)化為自身更小的形式來(lái)得到問(wèn)題解的方法稱為遞歸算法，遞歸算法必須包含一個(gè)或多個(gè)基本公式。
  遞歸算法的應(yīng)用條件如下：
  （1）可以將要解決的問(wèn)題轉(zhuǎn)化為另一個(gè)新問(wèn)題，而解決這個(gè)新問(wèn)題的方法與原問(wèn)題的解決方法相同，并且被處理的對(duì)象的某些參數(shù)是有規(guī)律地遞增或遞減的。其中轉(zhuǎn)化的過(guò)程成為一般公式。
  （2）必須有終止遞歸的條件（基本公式），即遞歸出口。
  編寫(xiě)遞歸算法必須做到以下幾點(diǎn)。
  ①確定限制條件或問(wèn)題的規(guī)模。
  ②確定基本公式。
  ③確定一般公式。
• 遞歸設(shè)計(jì)方法二
  對(duì)于一個(gè)輸入規(guī)模為n的函數(shù)或問(wèn)題，用某種方法把輸入分割成k個(gè)子集，從而產(chǎn)生k個(gè)字問(wèn)題，分別求解這個(gè)k個(gè)子問(wèn)題，得出k個(gè)問(wèn)題的字解。有些子問(wèn)題可以直接得到解決，有些子問(wèn)題的解決方法與原問(wèn)題相同，再用某種方法把它們組合成原來(lái)問(wèn)題的解。
  遞歸文章詳細(xì)解析+題目介紹

3.2.棧與函數(shù)調(diào)用

（1）函數(shù)的嵌套調(diào)用
main()->fun()->gun()
問(wèn)題1：每個(gè)函數(shù)調(diào)用完成后，執(zhí)行流程轉(zhuǎn)向何處？
問(wèn)題2：執(zhí)行流程轉(zhuǎn)向被調(diào)函數(shù)后，繼續(xù)向下執(zhí)行，被調(diào)用的參數(shù)的內(nèi)部變量在哪里保存？
（2）函數(shù)調(diào)用的管理
用高級(jí)語(yǔ)言編寫(xiě)的程序中，主調(diào)函數(shù)與被調(diào)函數(shù)之間的信息交換通過(guò)棧來(lái)進(jìn)行。當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該別調(diào)函數(shù)之前，需先完成三件事。

• 將所有的實(shí)參和返回地址等信息傳遞給被調(diào)函數(shù)保護(hù)。
• 為被調(diào)函數(shù)的局部變量分配存儲(chǔ)區(qū)。
• 將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口。

從被調(diào)函數(shù)返回調(diào)用函數(shù)之前，也應(yīng)該完成三件事。

• 保存被調(diào)函數(shù)的計(jì)算結(jié)果。
• 釋放被調(diào)函數(shù)中形參和局部變量的存儲(chǔ)區(qū)。
• 依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到主調(diào)函數(shù)。

多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：先調(diào)用函數(shù)后返回，后調(diào)用函數(shù)先返回。系統(tǒng)對(duì)調(diào)函數(shù)的內(nèi)存管理實(shí)行的“棧式管理”。

3.3.遞歸工作與遞歸函數(shù)

遞歸函數(shù)是指定義在一個(gè)函數(shù)的過(guò)程中直接或間接地調(diào)用該函數(shù)本身。

遞歸工作棧的記錄是一個(gè)結(jié)構(gòu)體類型的數(shù)據(jù)，包括：
（1）上一層函數(shù)調(diào)用的放回地址。
（2）局部變量（包括參數(shù)）值。
系統(tǒng)工作棧的棧頂工作記錄對(duì)應(yīng)的是當(dāng)前正在調(diào)用的函數(shù)。每調(diào)一次函數(shù)，將函數(shù)的返回地址和局部變量（包括參數(shù)）表形成一個(gè)遞歸工作記錄壓入系統(tǒng)工作棧。每調(diào)用完一次函數(shù)，將系統(tǒng)工作棧的棧頂工作記錄彈出，直至系統(tǒng)工作棧為空。棧空表明遞歸函數(shù)調(diào)用結(jié)束。

遞歸算法的特點(diǎn)如下。

• 優(yōu)點(diǎn)：程序易于設(shè)計(jì)，程序結(jié)構(gòu)簡(jiǎn)單精煉。
• 缺點(diǎn)：遞歸算法較難理解，可讀性差；程序運(yùn)行速度慢，占用相當(dāng)多的系統(tǒng)資源空間。

3.4.遞歸到非遞歸的轉(zhuǎn)換

遞歸的缺點(diǎn)很明顯，所以能用循環(huán)就不要用遞歸。
（1）直接轉(zhuǎn)換法。
如果遞歸算法是直接求值，不需要回溯，則只需要變量保存中間的結(jié)果，將遞歸結(jié)果改為循環(huán)結(jié)構(gòu)。
（2）間接轉(zhuǎn)換法
按照遞歸的執(zhí)行規(guī)律進(jìn)行轉(zhuǎn)換，將遞歸調(diào)用語(yǔ)句改為進(jìn)棧操作，將每次遞歸返回調(diào)用后的后續(xù)執(zhí)行語(yǔ)句改為出棧操作。

//將任意一個(gè)整數(shù)按數(shù)字字符顯示的遞歸函數(shù)如下void change(int x)
{int n;if (n = x / 10){change(n);//進(jìn)棧}putchar(x % 10 + 48);//出棧
}
//轉(zhuǎn)換成非遞歸
void change(int x)
{int n;STACK s;s = NULL;if (x == 0){putchar(x + 48);return;}while (x){//進(jìn)棧push(s, x % 10);x /= 10;}while (!empty(s)){pop(s, n);//出棧putchar(n + 48);}putchar('\n');
}