【文章內(nèi)容簡(jiǎn)介】 中綴表達(dá)式計(jì)算相同的結(jié)果值： 97. ? 用后綴表示法進(jìn)行求值過程中，其堆棧的變換如圖所示： 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法 算法思想： 1. 中綴表達(dá)式保存在字符串 S1中，后綴表達(dá)式保存在 S2中 2. 在轉(zhuǎn)換過程中，設(shè)一保存運(yùn)算符的堆棧，保存在掃描過程所遇到的運(yùn)算符， 3. 在棧底放一特殊字符（如 @），讓它具有最低的運(yùn)算符優(yōu)先級(jí)，以便作為標(biāo)志彈出運(yùn)算符過程的結(jié)束符。 4. 在掃描時(shí)，遇到非運(yùn)算符的數(shù)字時(shí)，將其直接添加到后綴表達(dá)式的字符串 S2中，并加空格分隔符 5. 在掃描時(shí)，若遇到括號(hào)，則先將其左括號(hào)，壓入堆棧保存，直到 遇到右括號(hào)，則將左括號(hào)之后壓入的運(yùn)算符依次彈出并加入到 S2中（每個(gè)運(yùn)算符用空格符分隔），再將左括號(hào)彈出。 6. 在掃描時(shí)，若遇到運(yùn)算符，則先與已壓入堆棧并位于棧頂?shù)倪\(yùn)算符比較，若其優(yōu)先級(jí)大于棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)，表明該運(yùn)算符的后一個(gè)運(yùn)算對(duì)象還沒有被掃描并放入到 s2串中，應(yīng)把它暫存于運(yùn)算符棧中，待它的后一個(gè)運(yùn)算對(duì)象從 s1串中讀出并寫入到 s2串中后，再另其出棧并寫入 s2串中 7. 若遇到的運(yùn)算符的優(yōu)先級(jí)小于等于棧頂運(yùn)算符的優(yōu)先級(jí)，這表明棧頂運(yùn)算符的兩個(gè)運(yùn)算對(duì)象已經(jīng)被保存到 s2串中，應(yīng)將棧頂運(yùn)算符退棧并寫入到 s2串中。 8. 對(duì)于新的棧頂運(yùn)算符仍繼續(xù)進(jìn)行比較和處理，直到被處理的運(yùn)算符的優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)為止，然后令該運(yùn)算符進(jìn)棧即可。 9. 掃描到 s1串結(jié)束時(shí)，則彈出棧內(nèi)的所有運(yùn)算符加入到 S2串中（除 @外） int precedence(char op)； // 函數(shù)聲明 void Change(char* s1, char* s2) //將字符串 s1中的中綴表達(dá)式轉(zhuǎn)換為 s2字符串中的后綴表達(dá)式 { //定義用于暫存運(yùn)算符的棧 R并初始化，該棧的元素類型為 char Struct StackSq R。 / //定義 i,j分別用于掃描 s1和指示 s2串中相應(yīng)字符的位置 int i=0,j=0。 //定義 ch保存 s1串中掃描到的字符，初值為第一個(gè)字符 char ch=s1[i]。 InitStack2(amp。R， 5)。 //給棧底放入’ @?字符，它具有最低優(yōu)先級(jí) 0 Push(amp。R,?@?)。 //依次處理中綴表達(dá)式中的每個(gè)字符 while(ch!=?\0?) { //對(duì)于空格字符不做任何處理，順序讀取下一個(gè)字符 if(ch==? ?) ch=s1[++i]。 //對(duì)于左括號(hào)，直接進(jìn)棧 else if(ch==?(?) { Push(amp。R,ch)。 ch=s1[++i]。 } //對(duì)于右括號(hào)，使括號(hào)內(nèi)的仍停留在棧中的運(yùn)算符依次出棧并寫入 s2 else if(ch==?)?) { while(Peek(amp。R)!=?(?) s2[j++]=Pop(amp。R)。 Pop(amp。R)。 //刪除棧頂?shù)淖罄ㄌ?hào) ch=s1[++i]。 } //對(duì)于四則運(yùn)算符，使暫存棧頂不低于 ch優(yōu)先級(jí)的運(yùn)算符依次出棧并寫 s2 else if(ch==?+?||ch==??||ch==?*?||ch==?/?) { char w=Peek(amp。R)。 while(Precedence(w)=Precedence(ch)) { // Precedence(w)函數(shù)返回運(yùn)算符形參的優(yōu)先級(jí) s2[j++]=w。 Pop(amp。R)。 w=Peek(amp。R)。 } Push(amp。R,ch)。 //把 ch運(yùn)算符寫入棧中 ch=s1[++i]。 } //此處必然為數(shù)字或小數(shù)點(diǎn)字符，否則為中綴表達(dá)式錯(cuò)誤 else { //若 ch不是數(shù)字或小數(shù)點(diǎn)字符則退出運(yùn)行 if((ch?0?||ch?9?) amp。amp。 ch!=?.?) { printf(中綴表達(dá)式表示錯(cuò)誤 !\n)。 exit(1)。 } //把一個(gè)數(shù)值中的每一位依次寫入到 s2串中 while((ch=39。039。 amp。amp。 ch=39。939。) || ch==39。.39。) { s2[j++]=ch。 ch=s1[++i]。 } //被放入 s2中的每個(gè)數(shù)值后面接著放入一個(gè)空格字符 s2[j++]=? ?。 } } //把暫存在棧中的運(yùn)算符依次退棧并寫入到 s2串中 ch=Pop(amp。R)。 while(ch!=?@?) { if(ch==?(?) { printf(expression error!\n)。 exit(1)。 } else { s2[j++]=ch。 ch=Pop(amp。R)。 } } //在后綴表達(dá)式的末尾放入字符串結(jié)束符 s2[j++]=?\0?。 } int precedence(char op){ switch(op){ case ?+?: case ??: return 1。 case ?*?: case ?\?: return 2。 case ?(?: case ?@?: default: return 0。 } } 例子 2 假定有一個(gè)中綴算術(shù)表達(dá)式： 3+4－ 5 6+(8－ 3／ 2) 3 (字符串： S1） 則轉(zhuǎn)換為后綴表達(dá)式為： 3 4 + 5 6 － 8 3 2 ／ － 3 + （字符串： S2） 在轉(zhuǎn)換過程中，其堆棧變化如圖所示： 167。 棧與遞歸 1. 遞歸 的定義 遞歸是數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)的一個(gè)方法， 遞歸方法用于解決： 可分解為結(jié)構(gòu)自相似的問題。 結(jié)構(gòu)自相似的問題 —— 構(gòu)成問題的部分與問題本身結(jié)構(gòu)相似。 有直接解法的特殊情況 —— 也即有不需要遞 歸循環(huán)并可直接求解的狀態(tài)。 問題特點(diǎn)：可分解為 與原問題“相似”的子問題 —— 遞歸。 求解過程： 原問題 → 遞歸求子問題 → 遞歸求更小的子問題 → 有直接解或已知條件 → 逆過程逐步回代求出結(jié)果 遞歸算法的表現(xiàn)形式：自己調(diào)用自己（直接或間接）。 遞歸算法的優(yōu)點(diǎn)：結(jié)構(gòu)清晰、簡(jiǎn)練。 {? 遞歸分為直接遞歸與間接遞歸兩種。如果一個(gè)算法 A顯式地調(diào)用自己則稱為直接遞歸。如果算法 A調(diào)用另一個(gè)算法 B，而算法 B又調(diào)用算法 A，則稱為間接遞歸調(diào)用。 ?遞歸算法設(shè)計(jì)的基本思路： 1. 對(duì)于已給出遞歸定義的問題，可根據(jù)定義得到遞歸算法。 ，根據(jù)結(jié)構(gòu)的特性也容易寫出遞歸算法。 ?在計(jì)算機(jī)系統(tǒng)中，執(zhí)行遞歸函數(shù)調(diào)用是通過使用棧來實(shí)現(xiàn)的。 ?遞歸算法的執(zhí)行過程中遞歸工作棧每一層需要保存的內(nèi)容括： 局部變量、實(shí)際參數(shù)、返回地址。 ?遞歸的執(zhí)行與遞歸棧 第一階段： 遞推 。原問題分析，逐步推進(jìn)， 到達(dá)已知條件。 第二階段： 回歸 。從已知條件出發(fā)逆遞推，求出結(jié) 果。 ? 遞推 、回歸過程互逆。需用棧記憶調(diào)用層次 ——遞歸工作棧 。 遞推過程，記錄各層調(diào)用參數(shù) —— 壓棧 回歸過程，逐層恢復(fù)各參數(shù) —— 退棧 一、已給出遞歸定義的問題，可通過定義直接設(shè)計(jì)程序 例 1 采用遞歸算法求解正整數(shù) n的階乘： n！ 由數(shù)學(xué)知識(shí)可知， n階乘的遞歸定義為：它等于 n乘以 n1的階乘，即 n!=n*(n1)!，并且規(guī)定 0的階乘為 1。設(shè)函數(shù) f(n)=n!，則 f(n)可表示為： 1 (n=0) f(n)= n*f(n1) (n0) 在這里 n=0為遞歸終止條件，使函數(shù)返回 1， n0實(shí)現(xiàn)遞歸調(diào)用，由 n的值乘以 f(n1)的返回值求出 f(n)的值。 { 用 C語言編寫出求解 n!的遞歸函數(shù)為： long f(int n) { if(n==0) return 1。 else return n*f(n1)。 } 上述調(diào)用和返回過程可形象地用圖 45表示。 圖 45 利用 f(4)調(diào)用 f(n)遞歸函數(shù)的執(zhí)行流程 二、對(duì)有遞歸結(jié)構(gòu)但沒有直接遞歸定義的問題，可根據(jù)問題的本身來設(shè)計(jì)出遞歸程序 例 45 求解迷宮問題 一個(gè)迷宮包含有 m行 n列個(gè)小方格，每個(gè)方格用 0表示可通行，用 1表示墻壁，即不可通行。迷宮中通常有一個(gè)入口和一個(gè)出口，設(shè)入口點(diǎn)的坐標(biāo)為 (1,1)，出口點(diǎn)的坐標(biāo)為(m,n)，當(dāng)然入口點(diǎn)和出口點(diǎn)的值應(yīng)均為 0，即均可通行。從迷宮中的某一個(gè)坐標(biāo)位置向東、南、西、北任一方向移動(dòng)一步（即一個(gè)方格）時(shí)，若前面的小方格為 0，則可前進(jìn)一步，否則通行受阻，不能前進(jìn)，應(yīng)按順時(shí)針改變?yōu)橄乱粋€(gè)方向移動(dòng)。求解迷宮問題是從入口點(diǎn)出發(fā)尋找一條通向出口點(diǎn)的路徑，并打印出這條路徑，即經(jīng)過的每個(gè)小方格的坐標(biāo)。如圖47(a)是一個(gè) 6 8的迷宮，入口點(diǎn)坐標(biāo)為 (1,1)，出口點(diǎn)坐標(biāo)為 (6,8)，其中的一條路徑為(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(3,5),(3,6),(4,6),(4,7),(5,7),(6,7),(6,8)。 ? 為了判斷從當(dāng)從迷宮中的一個(gè)位置（稱它為當(dāng)前位置）前進(jìn)到下一個(gè)位置時(shí)，下一個(gè)位置相對(duì)于當(dāng)前位置的位移量（包括行位移量和列位移量），用一 個(gè) 4 2的整型數(shù)組 move來存儲(chǔ)位移量數(shù)據(jù)， ?在求解迷宮問題時(shí)，還需要使用一個(gè)與存儲(chǔ)迷宮數(shù)據(jù)的 maze數(shù)組同樣大小的輔助數(shù)組 mark，用它來標(biāo)識(shí)迷宮中對(duì)應(yīng)位置是否被訪問過。該數(shù)組每個(gè)