C語(yǔ)言表達(dá)式求值

1、實(shí)驗(yàn)四 算術(shù)表達(dá)式求值運(yùn)算器一、實(shí)驗(yàn)?zāi)康膸椭鷮W(xué)生熟練掌握棧的基本操作，并通過用算符優(yōu)先法對(duì)表達(dá)式求值的過程深刻領(lǐng)會(huì)用棧解決實(shí)際問題的基本方法。二、實(shí)驗(yàn)內(nèi)容編寫程序?qū)崿F(xiàn)從鍵盤終端輸入語(yǔ)法正確的算術(shù)表達(dá)式，計(jì)算出表達(dá)式的值。為了避免算符的二義性，可以假設(shè)表達(dá)式中只包含實(shí)型正常數(shù)運(yùn)算符包括加、減、乘、除四種基本運(yùn)算，可以包含圓括號(hào)。三、實(shí)驗(yàn)儀器微型計(jì)算機(jī)實(shí)驗(yàn)用編程語(yǔ)言：Turbo C 2.0，Borland C 3.0等以上版本四、實(shí)驗(yàn)原理1、算術(shù)四則運(yùn)算法則： 先乘除后加減 從左至右 先括號(hào)內(nèi)后括號(hào)外 2、方法：對(duì)運(yùn)算符建立優(yōu)先關(guān)系矩陣，按優(yōu)先關(guān)系對(duì)表達(dá)式進(jìn)行處理。 算符：運(yùn)算符和界符。根據(jù)法則1

2、：對(duì)于兩個(gè)相鄰運(yùn)算符，乘除優(yōu)先于加減。 根據(jù)法則2：乘除優(yōu)先級(jí)相同，加減優(yōu)先級(jí)相同。相鄰兩個(gè)同級(jí)運(yùn)算符左優(yōu)先。 根據(jù)法則3：“（”前面的運(yùn)算符優(yōu)先級(jí)低于“（”的優(yōu)先級(jí)。“（”的優(yōu)先級(jí)低于右邊相鄰算符。“）”左邊的算符高于“）”的優(yōu)先級(jí)。由于“（”和“）”必須成對(duì)出現(xiàn)，令它們的優(yōu)先性相同。 為了處理的方便，假設(shè)表達(dá)式以“”開始和結(jié)束，輸入表達(dá)式的一般形式為：#表達(dá)式#如： #5.3+4.2*(7.6+4.5)#規(guī)定開始的“”的優(yōu)先性低于所有其它算符，所有其它算符的優(yōu)先性高于結(jié)束的“”。根據(jù)假設(shè)，表達(dá)式開始的“#”和結(jié)束的“#”必須成對(duì)出現(xiàn)，所以也令它們的優(yōu)先性相同。對(duì)于一個(gè)正確的表達(dá)式，“)”不

3、可能與“（”相鄰，“（”不可能與結(jié)束的“#”相鄰，開始的“#”不可能與“）”相鄰，它們之間沒有優(yōu)先性，程序應(yīng)具有這種判斷能力。根據(jù)上面的討論，可用表1所示的算符優(yōu)先關(guān)系矩陣來描述算符之間的優(yōu)先關(guān)系，其中，用“”表示表達(dá)式中前一個(gè)算符的優(yōu)先性高于后一個(gè)算符的優(yōu)先性，用“”表示表達(dá)式中前一個(gè)算符的優(yōu)先性低于后一個(gè)算符的優(yōu)先性，用“=”表示表達(dá)式中前一個(gè)算符的優(yōu)先性與后一個(gè)算符的優(yōu)先性相同。若兩個(gè)算符之間無優(yōu)先性，用空白表示。表1：算符優(yōu)先關(guān)系矩陣=)=/*-+#)(/*-+3、算符表示為了使算符與優(yōu)先關(guān)系矩陣的行列號(hào)對(duì)應(yīng)，把表達(dá)式中可能有的算符放入一維數(shù)組中，可以用字符在一維數(shù)組中的下標(biāo)作為字符的

4、標(biāo)識(shí)碼。本計(jì)算中，算法表示如下：*/()+ 0 1 2 3 4 5 6即用0表示算符“”，用1表示算符“”，等。定義的字符數(shù)組為：char a=+,-,*,/,(,),#;4、優(yōu)先關(guān)系矩陣的表示大于關(guān)系用1表示小于關(guān)系用1表示等于關(guān)系用0表示若兩個(gè)算符間不存在關(guān)系，則用一個(gè)特定的數(shù)值表示，如用整數(shù)的上限值32767表示，可定義一個(gè)宏常量來表示： #define NO 32767則其優(yōu)先關(guān)系矩陣為：int PriorityTable77= 1, 1,-1,-1,-1, 1, 1 , 1, 1,-1,-1,-1, 1, 1 , 1, 1, 1, 1,-1, 1, 1 , 1, 1, 1, 1,-1

5、, 1, 1 , -1,-1,-1,-1,-1, 0, NO, 1, 1, 1, 1,NO, 1, 1 , -1,-1,-1,-1,-1,NO, 0 ; 5、算術(shù)表達(dá)式求值算法的實(shí)現(xiàn)原理處理過程： 設(shè)置兩個(gè)棧：操作數(shù)棧OPND和運(yùn)算符棧OPTR。 1、首先置操作數(shù)棧為空棧，把“#”移進(jìn)運(yùn)算符棧（實(shí)際放入棧中的是字符“#”在字符數(shù)組中的下標(biāo)，對(duì)其它算符也是一樣）。 2、從左至右掃描表達(dá)式，凡遇到操作數(shù)一律進(jìn)OPND棧；若遇到運(yùn)算符，則把棧頂運(yùn)算符與掃描運(yùn)算符的優(yōu)先數(shù)進(jìn)行比較：若 -1：掃描運(yùn)算符進(jìn)OPTR棧 0： 若“（”和“）”，棧頂符號(hào)出棧；若為#，運(yùn)算結(jié)束。 1： 取OPND棧頂操作數(shù)與O

6、PTR棧頂算符進(jìn)行運(yùn)算，參與運(yùn)算的操作數(shù)和運(yùn)算符出棧，運(yùn)算結(jié)果進(jìn)OPND棧 NO:表示表達(dá)式有錯(cuò)。 若表達(dá)式處理完，OPTR棧為#，OPND棧中只剩一項(xiàng)，表示表達(dá)式的運(yùn)算結(jié)果，則分析成功。若達(dá)不到這種狀態(tài)，表明表達(dá)式有錯(cuò)。五、實(shí)現(xiàn)1、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) 假設(shè)一個(gè)表達(dá)式不可能很長(zhǎng)，如不超過屏幕上一行的寬度（80個(gè)字符），在對(duì)表達(dá)式處理之前先把表達(dá)式放入一個(gè)一維字符數(shù)組中，用戶可以不輸入表達(dá)式前后的“#”，由處理程序自動(dòng)加入。由于表達(dá)式的長(zhǎng)度有限，運(yùn)算符棧和操作數(shù)棧的長(zhǎng)度野優(yōu)先，假定不超過20，所以都采用順序存儲(chǔ)結(jié)構(gòu)比較合適。用C語(yǔ)言可定義如下：#define EXPLENGT 100#define S

7、TACKSIZE 20char exprEXPLENGT;int OPTRSTACKSIZE; /運(yùn)算符棧，元素為運(yùn)算符對(duì)應(yīng)的整數(shù)編碼double OPNDSTACKSIZE； /操作數(shù)棧，元素為表達(dá)式中的運(yùn)算數(shù)據(jù) 2、運(yùn)算符宏定義為了判斷運(yùn)算符的方便，增強(qiáng)程序的可讀性，定義如下宏常量：#define PLUS 0 /運(yùn)算符+#define MINUS 1 /運(yùn)算符-#define POWER 2 /運(yùn)算符*#define DIVIDE 3 /運(yùn)算符/#define LEFTP 4 /運(yùn)算符(#define RIGHP 5 /運(yùn)算符）#define STARTEND 6 /運(yùn)算符#define

8、 DIGIT 7 /數(shù)字字符 #define POINT 8 /小數(shù)點(diǎn)3、基本功能(1) 輸入算術(shù)表達(dá)式(2) 計(jì)算表達(dá)式的值4、輔助功能（1）菜單選擇（2）獲取字符類型編碼 5、程序結(jié)構(gòu) 該程序由5個(gè)函數(shù)組成，其中主函數(shù)1個(gè)，基本功能函數(shù)2個(gè)，輔助功能函數(shù)2個(gè)。函數(shù)間的調(diào)用關(guān)系圖1所示。mainexcute InputExpressionnemuGetCharType 圖1 程序結(jié)構(gòu)圖 6、函數(shù)說明（1）主函數(shù)main 功能：根據(jù)菜單選擇確定要操作的內(nèi)容： 表達(dá)式輸入 表達(dá)式計(jì)算 計(jì)算結(jié)果輸出 退出系統(tǒng)（2）菜單選擇函數(shù)：menu功能：構(gòu)造功能菜單，并選擇下一步要操作的功能。格式： int

9、menu(void)參數(shù)：無參數(shù)。返回值：14中的一個(gè)序號(hào)。 可供選擇的功能如下：1-input expression 表示輸入表達(dá)式 2-calculation expression 表示計(jì)算表達(dá)式 3-print result 表示輸出計(jì)算結(jié)果 4-Quit 表示退出系統(tǒng)，結(jié)束程序的運(yùn)行 （3）表達(dá)式輸入函數(shù)：InputExpression功能：輸入表達(dá)式，并在表達(dá)式前后加上符號(hào)“”格式：void InputExpression(char str) 參數(shù)：char str存放輸入的表達(dá)式返回值：無（4）表達(dá)式計(jì)算函數(shù)：excute 功能:完成表達(dá)式的計(jì)算格式：int excute(char

10、 *str,double *Result)參數(shù)：char *str要計(jì)算的表達(dá)式字符串 double *Result計(jì)算結(jié)果值 返回值：1計(jì)算成功 0計(jì)算失?。?）確定當(dāng)前字符類型函數(shù)：GetCharType 功能：確定當(dāng)前要處理的字符的類型格式：int GetCharType(char ch)參數(shù)：char ch當(dāng)前要處理的字符返回值：若為算符，返回字符的編碼（一維數(shù)組下標(biāo)） 若為數(shù)字，返回符號(hào)常熟DIGIT（數(shù)字） 若為小數(shù)點(diǎn)，返回符號(hào)常熟POINT（小數(shù)點(diǎn)） 若不是定義的表達(dá)式的字符，返回1。六、算法描述1、表達(dá)式計(jì)算算法描述設(shè)棧頂指針：int topTr運(yùn)算符棧頂指針 topNd操作數(shù)

11、棧頂指針表達(dá)式字符指針：int pp指向表達(dá)式中當(dāng)前要處理的字符開始時(shí)，把表達(dá)式開始符“#”（編碼）放入棧中。設(shè)當(dāng)前要處理的字符類型為CharType。以當(dāng)前要處理的字符為參照來確定下一步要作的處理：若當(dāng)前字符為非法字符：則結(jié)束處理，返回出錯(cuò)標(biāo)志（0）；若當(dāng)前字符是數(shù)字：表示遇到表達(dá)式中的操作數(shù)，則識(shí)別出該操作數(shù)；若當(dāng)前字符是小數(shù)點(diǎn)：表示遇到以小數(shù)點(diǎn)開頭的操作數(shù)，則識(shí)別出該操作數(shù)；若當(dāng)前字符是、*、/運(yùn)算符：則用棧頂運(yùn)算符與當(dāng)前運(yùn)算符比較優(yōu)先性：若對(duì)應(yīng)的數(shù)組元素為1，則當(dāng)前運(yùn)算符（運(yùn)算符編碼）進(jìn)棧，調(diào)整pp指向下一個(gè)字符。若對(duì)應(yīng)的數(shù)組元素為1，則取運(yùn)算符棧頂運(yùn)算符和操作數(shù)棧頂操作數(shù)進(jìn)行運(yùn)算，參

12、與運(yùn)算的運(yùn)算符和操作數(shù)出棧，運(yùn)算結(jié)果進(jìn)操作數(shù)棧。實(shí)現(xiàn)為： OPNDtopNd-2=OPNDtopNd-2 op OPBDtopNd-1; topNd-; topTr-;若當(dāng)前字符是左括號(hào)(: 則左括號(hào)進(jìn)棧，pp指向下一個(gè)字符若當(dāng)前字符是右括號(hào)）：若棧頂是左括號(hào)，則左括號(hào)出棧，pp指向下一個(gè)字符若棧頂是運(yùn)算符，則取運(yùn)算符棧頂運(yùn)算符和操作數(shù)棧頂操作數(shù)進(jìn)行運(yùn)算，參與運(yùn)算的運(yùn)算符和操作數(shù)出棧，運(yùn)算結(jié)果進(jìn)操作數(shù)棧。實(shí)現(xiàn)為： OPNDtopNd-2=OPNDtopNd-2 op OPBDtopNd-1; topNd-; topTr-; 重復(fù)該操作，直到棧頂出現(xiàn)左括號(hào)“（”。若棧頂是，則左括號(hào)和右括號(hào)不配對(duì)

13、，結(jié)束處理，返回出錯(cuò)標(biāo)志（0）若當(dāng)前字符為：依次從運(yùn)算符棧取出運(yùn)算符和從操作數(shù)棧取出操作數(shù)進(jìn)行計(jì)算，直到運(yùn)算符棧的棧頂為為止。若運(yùn)算符棧頂為，當(dāng)前字符也為，則表達(dá)式計(jì)算結(jié)束，返回計(jì)算結(jié)果值和計(jì)算成功標(biāo)志（1）。2、字符型數(shù)字常數(shù)轉(zhuǎn)換為數(shù)值型常數(shù)的方法因?yàn)槌绦蛱幚淼谋磉_(dá)式是以字符串形式出現(xiàn)的，表達(dá)式中每個(gè)數(shù)值型常數(shù)也是有一個(gè)一個(gè)的數(shù)字字符組成。處理程序必須把字符串形式的常數(shù)轉(zhuǎn)換為數(shù)值形式的常數(shù)。（1）整數(shù)的轉(zhuǎn)換方法我們知道，一個(gè)數(shù)值型常數(shù)3256可以表示為： 3256=(3*10+2)*10+5)*10+6相應(yīng)的，一個(gè)字符串型的數(shù)字常數(shù)“3256”轉(zhuǎn)換為數(shù)值型常數(shù)可以表示為： (3-48)*10

14、+(2-48)*10+(5-48)*10+(6-48)每個(gè)字符的ASCII碼指減去48就是該字符對(duì)應(yīng)數(shù)字值。實(shí)現(xiàn)方法：依次讀入數(shù)字字符，用前面讀入子字符串對(duì)應(yīng)的數(shù)值型值乘以10，再加上當(dāng)前字符的數(shù)字值，就是當(dāng)前讀入子字符串對(duì)應(yīng)的數(shù)值型值。用C語(yǔ)言描述如下：number=0; while(strpp=0 & strpp=0 & strpp=0 & strpp=0 & strpp=9) /處理實(shí)數(shù)的小數(shù)部分 number=number+(strpp-48)/temp; temp=temp*10; pp+; 七、思考題 1、若表達(dá)式中的數(shù)據(jù)帶有正負(fù)號(hào)的實(shí)數(shù)字符串該怎樣進(jìn)行轉(zhuǎn)換？2、對(duì)于指數(shù)形式的實(shí)數(shù)

15、字符串該怎樣進(jìn)行轉(zhuǎn)換？八、部分函數(shù)代碼#include#include #include #define PLUS 0#define MINUS 1#define POWER 2#define DIVIDE 3#define LEFTP 4#define RIGHP 5#define STARTEND 6#define DIGIT 7#define POINT 8#define NUM 7#define NO 32767#define STACKSIZE 20/運(yùn)算符 char a=+,-,*,/,(,),#; /優(yōu)先關(guān)系矩陣，規(guī)定：=為0,為1,為-1,空為NO int PriorityTa

16、ble77= 1, 1,-1,-1,-1, 1, 1, 1, 1,-1,-1,-1, 1, 1, 1, 1, 1, 1,-1, 1, 1, 1, 1, 1, 1,-1, 1, 1, -1,-1,-1,-1,-1, 0, NO, 1, 1, 1, 1,NO, 1, 1, -1,-1,-1,-1,-1,NO, 0 ; int menu(void) ;/*int n;printf(nn);printf(MENUn);printf(*n);printf(operationsn);printf(1.輸入表達(dá)式n);printf(2.計(jì)算表達(dá)式n);printf(3.輸出計(jì)算結(jié)果n);printf(4.退

17、出n);printf(*n);printf(choice(1,2,3,4):);scanf(%d,&n);return n;*/ /*/ /* 輸入表達(dá)式函數(shù) */ /*/void InputExpression(char str) int len; printf(Input expression string:n); scanf(%s,str); len=strlen(str); strlen=#; strlen+1=0; /*/ /* 確定當(dāng)前字符類型 */ /*/ /* 若為運(yùn)算符，則返回運(yùn)算符在運(yùn)算符數(shù)組中的序號(hào) */ /* 若為數(shù)字字符，則返回DIGIT */ /* 若為小數(shù)點(diǎn)字符,

18、則返回POINT */ /* 否則為非法字符,返回-1 */ /*/int GetCharType(char ch) int i; for(i=0;i=0 & ch=0 & strpp=0 & strpp=0 & strpp=9) number=number+(strpp-48)/temp; temp=temp*10; pp+; OPNDtopNd=number; topNd+; break; case PLUS: /+ case MINUS: /- case POWER: /* case DIVIDE: /while(PriorityTableOPTRtopTr-1CharType=1) i

19、f(OPTRtopTr-1=PLUS)number=OPNDtopNd-2+OPNDtopNd-1;else if(OPTRtopTr-1=MINUS)number=OPNDtopNd-2-OPNDtopNd-1;else if(OPTRtopTr-1=POWER)number=OPNDtopNd-2*OPNDtopNd-1;else if(OPTRtopTr-1=DIVIDE)number=OPNDtopNd-2/OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;OPTRtopTr=CharType;

20、topTr+;pp+;break;case LEFTP: /(OPTRtopTr=LEFTP;topTr+;pp+;break;case RIGHP: /)while(OPTRtopTr-1!=LEFTP)if(OPTRtopTr-1=PLUS)number=OPNDtopNd-1+OPNDtopNd-2;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;else if(OPTRtopTr-1=MINUS)number=OPNDtopNd-2-OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd

21、=number;topNd+;return number;else if(OPTRtopTr-1=POWER)number=OPNDtopNd-2*OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;else if(OPTRtopTr-1=DIVIDE)number=OPNDtopNd-2/OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;topTr-;pp+;break; case STARTEND: /遇到表達(dá)

22、式結(jié)束符while(OPTRtopTr-1!=STARTEND)if(OPTRtopTr-1=PLUS)number=OPNDtopNd-1+OPNDtopNd-2;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;else if(OPTRtopTr-1=MINUS)number=OPNDtopNd-2-OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;else if(OPTRtopTr-1=POWER)number=OPNDtopNd-2*OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;else if(OPTRtopTr-1=DIVIDE)number=OPNDtopNd-2/OPNDtopNd-1;topNd-;topNd-;topTr-;OPNDtopNd=number;topNd+;return number;pp+;break; if(topNd=1) *Result=OPND0; return(1); else