【正文】 用兩種方式實現(xiàn)表達式自動計算 1 一、設計思想 （一）中綴轉后綴的設計思想 設計一個能實現(xiàn)表達式自動求值計算，算術表達式由操作數(shù)、算符和括號組成。由于運算符的優(yōu)先級不同還要 考慮 括號。所以表達式不可能一直的從左到右進行，所以就借助棧來實現(xiàn)這個表達式的求值。 首先要把算術表達式變換成與之等值的無括號表達式，也就是中綴轉后綴，它也是這個算法的關鍵。設計兩個棧，一個為字符型的，存放運算符，用以將算術表達式變成無括號的表達式；另一個浮點型的，存放操作數(shù)，用以對無符號的表達式進行求值。我們要假設運算符的優(yōu)先級： ( ) , * /, + 。首先將一 左括號‘ (’入棧，作為棧底元素；接著從左到右對算術表達式進行掃描。每次讀一位，若遇到左括號‘（’，則進棧；若遇到的是操作數(shù)，則立即輸出；若又遇到運算符，如果它的優(yōu)先級比棧頂元素的優(yōu)先級數(shù)高的話，則直接進棧，否則輸出棧頂元素，直到新的棧頂元素的優(yōu)先級數(shù)比它低的，然后將它壓棧；若遇到是右括號‘）’，則將棧頂?shù)倪\算符輸出，直到棧頂?shù)脑貫椤ā?，然后，左右括號互相底消；到設計的結束標志的時候表示表達式已經掃描完畢，表達式已經全部輸入，將棧中的運算符全部輸出，刪除棧底的左括號。以上完成了中綴表達式轉后綴表達式，輸出 無括號的后綴表達式。 讀后綴表達式，若遇數(shù)值，操作數(shù)進棧；若遇運算符，讓操作數(shù)棧的棧頂和次棧頂依次出棧并與此運算符進行運算，運算結果入操作數(shù)棧；重復這個步驟，直到遇到結束標志，則此時棧中的結果便是所求的后綴表達式的值，接著輸出結果。以上就是設計這個算法的主要的思想。 (二 ) 直接計算的設計思想 直接計算其實跟上一個相似， 它是在 上面掃兩遍的思想進行修改的得來。 首先，要建立兩個棧， 一個為字符型的，存放運算符，另一個浮點型的，存放操作數(shù)，我們開始對 表達式 進行掃描。首先 要 確定 運算符的優(yōu)先級： （、）、 *、 /、 +、 。 如果掃描到的是數(shù)字符號，把它們轉換成浮點型數(shù)據(jù)或其他可運算的數(shù)據(jù)類型，存入操作數(shù)棧中。如果掃描到的是運算符號，第一個運算符進棧，遇到‘（’存入運算符棧中，我們按照第一種算法的方法將 表達式依次 掃描。只不過不同的是，當每取得的一個運算符的時候，都要與棧頂?shù)倪\算符進行比較，如果它的優(yōu)先級小于棧頂運算符優(yōu)先級時，取出棧頂運算符并從操作數(shù)棧中取棧頂兩個數(shù)進行運算，得到的結果則要存回操作數(shù)棧，就這樣邊掃描邊比較，再進行計算。遇到“）”對運算符的處理相同。掃描結束后，把運算符棧的元素和操作數(shù)棧里的數(shù)進行運算。每次的運 算結果再放入操作數(shù)棧，一直到計算到運算符?？?。最后操作數(shù)棧的棧頂留下的操作數(shù)即表達式的計算結果。 以上就是 直接計算表達式的思路。 用兩種方式實現(xiàn)表達式自動計算 2 二、算法流程圖 （一） 中綴轉后綴算法的流程圖 輸 入輸 入 表 達 式判 斷 數(shù) 組整 數(shù)轉 化 成 浮 點 型小 數(shù)操 作 符后 綴 數(shù) 組優(yōu) 先 級 大 于 棧頂操 作 符 進 棧讀 完 表 達 式后 綴 表 達式輸 出是優(yōu) 先 級 大 于棧 頂 或 棧 空否出 棧是 判 斷 數(shù) 組 數(shù)讀 表 達 式操 作 符操 作 數(shù) 棧計 算 結 果2 個數(shù)1 個符號 圖 1 中綴轉后綴算法的流程圖 流程圖說明： 該流程圖分兩部 分 成，第一部 分 是中綴轉后綴部 分 ，第二部 分 是 用于 后綴表達式求值的。 用兩種方式實現(xiàn)表達式自動計算 3 （二） 直接計算 算法的流程圖 輸 入輸 入 表 達 式判 斷 數(shù) 組轉 化 成 浮 點 型數(shù)操 作 符操 作 數(shù) 棧計 算 結 果優(yōu) 先 級 大 于 棧頂操 作 符 進 棧輸 出是優(yōu) 先 級 大 于棧 頂 或 棧 空否出 棧 ( 1 個 )2個數(shù) 圖 2 接計算 算法的流程圖 流程圖說明 ：該流程圖進過圖 1 改進 得到，只是缺少中綴轉后綴的部分。 三、源代碼 下面給出的是用 中綴轉后綴 算法實現(xiàn)的程序的源代碼： include define N 50 typedef struct StackArray{ float data[N]。 int top。 }StackArray。 /*定義操作數(shù)棧 */ typedef struct StackChar{ char data[N]。 int top。 用兩種方式實現(xiàn)表達式自動計算 4 }StackChar。 /*定義操作符棧 */ StackArray *InitNum() /*初始化數(shù)值棧 */ { StackArray *p = (StackArray *)malloc(sizeof(StackArray))。 /*取一段內存賦予數(shù)值棧 */ ptop=1。 return p。 /*返回 */ } StackChar *InitChar() /*初始化操作符棧 */ { StackChar *p=(StackChar *)malloc(sizeof(StackChar))。 /*取一段內存賦予數(shù)值棧 */ ptop=1。 return p。 } int PushNum(StackArray *p,float value) /*定義入棧函數(shù) */ { if(ptop501) { ptop+=1。 pdata[ptop]=value。 /*棧頂 */ return 1。 } else { return 0。 } } int PushChar(StackChar *p,char value) /*操作符入棧 */ { if(ptop501) { ptop+=1。 pdata[ptop]=value。 /*入棧為棧頂 */ return 1。 } else { return 0。 /*返回值 */ } } 用兩種方式實現(xiàn)表達式自動計算 5 int PopNum(StackArray *p,float *value) /*操作數(shù)出棧 */ { if(ptop=0) /*判斷棧是否為空 */ { *value=pdata[ptop]。 ptop=1。 } return 1。 } int PopChar(StackChar *p,char *q) /*操作符出棧函數(shù) */ { if(ptop=0) /*定義操作符棧 */ { *q=pdata[ptop]。 ptop=1。 } return 1。 } float VisitNum(StackArray *p) /*定義數(shù)值棧遍歷函數(shù) */ { if(ptop!=1) return pdata[ptop]。 else return 0。 } char vis