1.括號匹配

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] != '}'){//非括號處理continue;}switch (str[k])//對括號進行匹配處理{case '(':case '{':case '['://遇到左括號進棧PushLinkStack(&S, str[k]);break;case ')'://遇到右圓括號if (S != NULL){GetTopStack(S, &e);if (e == '('){PopLinkStack(&S, &e);//棧頂是左圓括號，匹配成功}else{flag = 0;//棧頂不是左圓括號，匹配失敗}}else{flag = 0;//棧空，匹配失敗}break;case ']'://遇到右方括號if (S != NULL){GetTopStack(S, &e);if (e == '['){PopLinkStack(&S, &e);//棧頂是左方括號，匹配成功}else{flag = 0;//棧頂不是左方括號，匹配失敗}}else{flag = 0;//?？?#xff0c;匹配失敗}break;case '}'://遇右花括號if (S != NULL){GetTopStack(S, &e);if (e == '}'){PopLinkStack(&S, &e);//棧頂是左右花括號，匹配成功}else{flag = 0;//棧頂不是左右花括號，匹配失敗}}else{flag = 0;//?？?#xff0c;匹配失敗}break;                      }//switch}//forif (flag == 1 && S == NULL){printf("括號匹配!\n");}else{printf("括號不匹配！\n");}
}

2.表達式求值

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

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

數(shù)學上的算法表達式通常包括操作數(shù)和運算符。

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

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

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

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

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

2.2.后綴表達式求值

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

int suffix_value(char a[])//a指向后綴表達式
{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++;//訪問下一個}PopLinkStack(&S, &result);return result;
}//suffix_value

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

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

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ù)表達式轉(zhuǎn)換成后綴表達式的算法如下：
【算法】

void Transformation(char a[], char suff[])
{//a指向算術(shù)表達式，以'#'結(jié)束，棧用于存放運算符//將a指向的算術(shù)表達式轉(zhuǎn)換成由suff指向的后綴表達式int i = 0;int k = 0;int n;char ch;LinkStack s;s = NULL;PushLinkStack(&s, '#');n = strlen(a);//在表達式的末尾添加一個#a[n] ='#';a[n + 1] = '\0';while (a[i] != '\0'){if (a[i] >= '0' && a[i] <= '9'){//是操作數(shù)，直接存入后綴表達式suff[k++] = a[i];}//是運算符else{switch (a[i]){case '(':PushLinkStack(&s, a[i]);//進棧break;case ')'://將左圓括號之上的運算符依次出棧并發(fā)送到后綴表達式，左圓括號只是出棧PopLinkStack(&s, &ch);while (ch != '('){suff[k++] = ch;PopLinkStack(&s, &ch);}break;/*比較表達式當前的運算符a[i]和棧頂運算符的ch的優(yōu)先級，如果a[i]高于ch，a[i]進棧；反之，棧內(nèi)高于a[i]的運算符依次出棧并發(fā)往后綴表達式直到棧頂運算符優(yōu)先級低，在將a[i]進棧*/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ù)是個位數(shù)。要計算任意實數(shù)，需要解決如下問題。
（1）后綴表達式中的操作數(shù)與操作數(shù)之間如何隔開。
（2）操作數(shù)棧的類型是什么？
（3）如何將一個數(shù)字串轉(zhuǎn)換為一個實數(shù)？
（4）操作數(shù)為負數(shù)的時，如何處理？
例如，算術(shù)表達式為-3+（-15.7+9）* 4.25 + 7/8.2
（1）先處理負數(shù)的情況。
原則：第一個字符為‘-’時，前面加0；‘("之后是’-‘，在’('之后加0。
（2）在操作數(shù)與操作數(shù)之間加空格。

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

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

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

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

3.棧與遞歸

3.1.遞歸算法

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

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

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

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

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

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

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

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

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

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

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

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

遞歸算法的特點如下。

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

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

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

//將任意一個整數(shù)按數(shù)字字符顯示的遞歸函數(shù)如下void change(int x)
{int n;if (n = x / 10){change(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){//進棧push(s, x % 10);x /= 10;}while (!empty(s)){pop(s, n);//出棧putchar(n + 48);}putchar('\n');
}