數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二_算術(shù)表達(dá)式求值實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目算術(shù)表達(dá)式求值學(xué)院：化學(xué)與材料科學(xué)學(xué)院專業(yè)班級(jí)：09級(jí)材料科學(xué)與工程系 PB0920603姓名：維谷學(xué)號(hào)：PB09206285 郵箱：指導(dǎo)教師：賈伯琪實(shí)驗(yàn)時(shí)間：2010年10月10日一、 需要分析問題描述：表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，它的實(shí)現(xiàn)是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示通過將數(shù)學(xué)表達(dá)式字符串轉(zhuǎn)化為后綴表達(dá)式，并通過后綴表達(dá)式結(jié)合棧的應(yīng)用實(shí)現(xiàn)對(duì)算術(shù)表達(dá)式進(jìn)行四則混合運(yùn)算。問題分析：在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號(hào)組成。由于不同的運(yùn)算符具有不同的優(yōu)先級(jí)，又要考慮括號(hào)，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)行。因而

2、在程序設(shè)計(jì)時(shí)，借助棧實(shí)現(xiàn)。設(shè)置運(yùn)算符棧（字符型）和運(yùn)算數(shù)棧（浮點(diǎn)型）輔助分析算符優(yōu)先關(guān)系。在讀入表達(dá)式的字符序列的同時(shí)完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理，然后進(jìn)行運(yùn)算數(shù)的數(shù)值轉(zhuǎn)換在進(jìn)行四則運(yùn)算。在運(yùn)算之后輸出正確運(yùn)算結(jié)果，輸入表達(dá)式后演示在求值中運(yùn)算數(shù)棧的棧頂數(shù)據(jù)變化過程，最后得到運(yùn)算結(jié)果。算法規(guī)定：輸入形式：一個(gè)算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號(hào)組成（以字符串形式輸入）。為使實(shí)驗(yàn)更完善，允許操作數(shù)為實(shí)數(shù)，操作符為（、）、.（表示小數(shù)點(diǎn)）、+、-、*、/、（表示乘方），用#表示結(jié)束。輸出形式：演示表達(dá)式運(yùn)算的中間結(jié)果和整個(gè)表達(dá)式的最終結(jié)果，以浮點(diǎn)型輸出。程序功能：對(duì)實(shí)數(shù)的加減乘除乘方運(yùn)算能正確的

3、運(yùn)算出結(jié)果，并能正確對(duì)錯(cuò)誤輸入和無定義的運(yùn)算報(bào)錯(cuò)，能連續(xù)測(cè)試多組數(shù)據(jù)。測(cè)試數(shù)據(jù)：正確輸入：12*（3.6/3+42-1）# 輸出結(jié)果：194.4 無定義運(yùn)算：12*（3.6/（22-4）+1）# 輸出結(jié)果：表達(dá)式出錯(cuò)，除數(shù)為0，無意義 錯(cuò)誤輸入：12+s# 輸出結(jié)果：ERROR！二、 概要設(shè)計(jì)擬采用兩種類型的展分別對(duì)操作數(shù)和操作符進(jìn)行操作。程序中將涉與下列兩個(gè)抽象數(shù)據(jù)類型：1、設(shè)定“操作數(shù)”的棧的抽象數(shù)據(jù)類型定義：ADTSqStack_f數(shù)據(jù)對(duì)象：D=數(shù)據(jù)關(guān)系：R1=<>|,i=2,，n約定端為棧頂，端為棧底?；静僮鳎?InitStack_f(&S) 操作結(jié)果：構(gòu)造一個(gè)空

4、棧S。 GetTop_f(&S,&e) 初始條件：棧S已存在。 操作結(jié)果：用e返回S的棧頂元素。 Push_f(&S，ch) 初始條件：棧S已存在。 操作結(jié)果：插入元素ch為新的棧頂元素。 Pop_f(&S,&e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。ADT SqStack_f2、設(shè)定“操作符”的棧的抽象數(shù)據(jù)類型定義：ADTSqStack_c數(shù)據(jù)對(duì)象：D=數(shù)據(jù)關(guān)系：R1=<>|,i=2,，n約定端為棧頂，端為棧底?；静僮鳎?InitStack_c(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧S。 GetTop_c(

5、&S,&e) 初始條件：棧S已存在。 操作結(jié)果：用e返回S的棧頂元素。 Push_c(&S，ch) 初始條件：棧S已存在。 操作結(jié)果：插入元素ch為新的棧頂元素。 Pop_c(&S,&e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。ADT SqStack_c3、本程序包含六個(gè)模塊1）主程序模塊void main( )初始化；while(命令=“繼續(xù)”)接受數(shù)據(jù)；處理數(shù)據(jù)；接受命令；2）棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型3）判斷運(yùn)算符優(yōu)先級(jí)模塊判斷運(yùn)算符的優(yōu)先級(jí)別4）后綴表達(dá)式轉(zhuǎn)換模塊將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，方便操作5）無括號(hào)表示式求

6、值運(yùn)算模塊根據(jù)后綴表達(dá)式求值，并輸出中間和最終結(jié)果6）運(yùn)算結(jié)果輸出模塊以正確形式輸出表達(dá)式的值三、 詳細(xì)設(shè)計(jì)1、主程序中需要的全程量#define TTACK_INIT_SIZE 100 /初始分配最大空間量#define STACKINCREMENT 10 /（默認(rèn)）增補(bǔ)空間量2、結(jié)點(diǎn)類型、指針類型typedef structfloat *base; /存儲(chǔ)實(shí)型數(shù)據(jù)元素的一位數(shù)組float *top; /棧頂指針int stacksize; /棧數(shù)組容量SqStack_f; /有序存儲(chǔ)實(shí)型的順序表類型typedef structchar *base; /存儲(chǔ)字符數(shù)據(jù)元素的一位數(shù)組char *

7、top; /棧頂指針int stacksize; /棧數(shù)組容量SqStack_c; /有序存儲(chǔ)字符型的順序表類型void InitStack_f(SqStack_f *s)void InitStack_f(SqStack_f *s)/構(gòu)造一個(gè)存儲(chǔ)實(shí)型（字符型）的空棧，預(yù)設(shè)空間為100，分配失敗就退出void GetTop_f(SqStack_f *s,float *e)void GetTop_c(SqStack_c *s,char *e)/若棧s不空，則以e帶值返棧頂元素，否則顯示錯(cuò)誤“ERROR”,并退出程序void Push_f(SqStack_f *s,float e)void Push

8、_c(SqStack_c *s,char e)/在s的棧頂插入新的棧頂元素e，若棧的當(dāng)前空間已滿，則追加存儲(chǔ)空間void Pop_f(SqStack_f *s,float *e)void Pop_c(SqStack_c *s,char *e)/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序其中部分操作的偽碼算法（由于比較類似，以浮點(diǎn)型的棧為例）void InitStack_f(SqStack_f *s)/構(gòu)造一個(gè)存儲(chǔ)實(shí)型的空棧，預(yù)設(shè)空間為100，分配失敗就退出s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!

9、s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void GetTop_f(SqStack_f *s,float *e)/若棧s不空，則以e帶值返棧頂元素，否則顯示錯(cuò)誤“ERROR”,并退出程序if(s->top=s->base)printf("ERROR!n");exit(1);*e=*(s->top-1);void Push_f(SqStack_f *s,float e)/在s的棧頂插入新的棧頂元素e，若棧的當(dāng)前空間已滿，則追加存儲(chǔ)空間if(s->to

10、p-s->base>=s->stacksize)s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float);if(!s->base)printf("OVERFLOW!n");exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void Pop_f(SqStack_f *s,float *e)/若棧s不空，則刪除棧

11、s的棧頂元素，用e帶值返回，否則退出程序if(s->top=s->base)exit(1);*e=*-s->top;3、判斷運(yùn)算符優(yōu)先級(jí)的算法：算符間的優(yōu)先關(guān)系如下：+-*/()#+>=<<<<>>->>=<<<>>*>>>=><>>/>>>>=<>>(<<<<<=)>>>>>>#<<<<<=偽碼算法：int pre

12、cede(char Top_char,char s1_char)/棧頂?shù)倪\(yùn)算符賦給Top_char，新讀入的運(yùn)算符賦給s1_char。判斷它們的優(yōu)先級(jí) /若棧頂運(yùn)算符優(yōu)先級(jí)高，則返回1，否則返回0int i,pre2;char op2;op0=Top_char; /棧頂?shù)倪\(yùn)算符賦給op0op1=s1_char; /新讀入的運(yùn)算符賦給op1for(i=0;i<2;i+)switch(opi)case'(':case')':prei=0;break; /將括號(hào)的優(yōu)先級(jí)設(shè)為0case'+':case'-':prei=1;break

13、; /將+ - 運(yùn)算符的優(yōu)先級(jí)設(shè)為1case'*':case'/':prei=2;break; /將* / 運(yùn)算符的優(yōu)先級(jí)設(shè)為2case'':prei=3;break; /將 運(yùn)算符的優(yōu)先級(jí)設(shè)為3if(pre0>=pre1) /棧頂元素優(yōu)先級(jí)高返回1return 1;elsereturn 0; /否則返回04、中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法：算法過程描述：1) 首先將左括號(hào)“(”壓進(jìn)棧，作為棧底元素；2) 從左而右對(duì)算數(shù)表達(dá)式進(jìn)行掃描，每次讀入一個(gè)字符s1i；3) 若遇到數(shù)字或小數(shù)點(diǎn)，則立即寫入s2i，若遇算數(shù)運(yùn)算符，將“”（空格）寫入s

14、2i；4) 遇到左括號(hào)“(”則壓棧；5) 若遇算術(shù)運(yùn)算符，如果它們的優(yōu)先級(jí)比棧頂元素高，則直接進(jìn)棧，否則彈出棧頂元素輸出到s2i，直到新棧頂元素的優(yōu)先級(jí)比它低，然后將它壓棧；6) 若遇到右括號(hào)“）”，則將棧頂元素輸出到s2i，直到棧頂元素為“（”，然后相互抵消；7) 當(dāng)掃描到“#”符號(hào)，表明表達(dá)式串已全部輸入，將棧中的運(yùn)算符全部輸出到s2i，并刪除棧頂元素。偽碼算法：void Translate(char *s1) /中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式char s280;SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);/初始化一個(gè)存儲(chǔ)字

15、符型的空棧，便于存儲(chǔ)運(yùn)算符Push_c(&Optr,'(');/ 首先將左括號(hào)“(”壓進(jìn)棧，作為棧底元素while(s1i!='#') /當(dāng)掃描到的不是“#”，即表達(dá)式串沒結(jié)束時(shí)if(s1i>='0' && s1i<='9' | s1i='.') /若果是數(shù)字或小數(shù)點(diǎn)則將其輸出給s2is2j+=s1i;if(s1i+1<'0' | s1i+1>'9') && s1i+1!='.')s2j+=' &

16、#39;elseswitch(s1i) /掃描到的是運(yùn)算符 case'(':Push_c(&Optr,s1i);break;/ 遇到左括號(hào)“(”則壓棧case')':Pop_c(&Optr,&t); /若遇到右括號(hào)“）”，則將棧頂元素輸出到s2iwhile(t!='(') /直到棧頂元素為“（”，然后相互抵消s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)/遇到算數(shù)運(yùn)算符則比較優(yōu)先級(jí)Pop

17、_c(&Optr,&t);/棧頂元素優(yōu)先級(jí)高，則彈出到s2is2j+=t;Push_c(&Optr,s1i);/棧頂元素優(yōu)先級(jí)低，直接壓棧i+;Pop_c(&Optr,&t);while(t!='(') /表達(dá)式串已結(jié)束，棧中的運(yùn)算符全部輸出到s2i，并刪除棧頂元素s2j+=t;Pop_c(&Optr,&t);for(i=0;i<j;i+) /將s2復(fù)制給s1s1i=s2i; s1i= '#'s1i+1='0'/為了方便打印后綴表達(dá)式，在字符串結(jié)尾加05、表示式求值運(yùn)算的算法：算法描述

18、：1） 讀入無括號(hào)的后綴表達(dá)式；2） 若為數(shù)值和小數(shù)點(diǎn)則將其聯(lián)合轉(zhuǎn)換為浮點(diǎn)型后進(jìn)棧（存放操作數(shù)）；3） 若為運(yùn)算符，讓棧頂元素和次頂元素與次運(yùn)算符進(jìn)行相應(yīng)的運(yùn)算，運(yùn)算結(jié)果打印并進(jìn)棧；4） 重復(fù)2）3）步驟，直到輸入為“#”，則此時(shí)棧中的結(jié)果便是所追求的表達(dá)式的值。數(shù)值轉(zhuǎn)換為實(shí)數(shù)的算法描述：1） 若為數(shù)字，則將其減去'0'的ASCII碼后就得到該數(shù)的數(shù)值，并暫存于一個(gè)變量m上；2） 若繼續(xù)為數(shù)字，也將其減去'0'的ASCII碼后就得到該數(shù)的數(shù)值，并將其值加上已存的m*10后的值再存于m；3） 重復(fù)2）步驟直到遇到小數(shù)點(diǎn)，從小數(shù)點(diǎn)后的數(shù)開始，在重復(fù)2）步驟的通知，也

19、記下小數(shù)點(diǎn)后的位數(shù)n；4） 當(dāng)遇到“”（空格）后，即表示此輪需轉(zhuǎn)換的數(shù)已讀入完畢，則將m除以10的你次方，則此時(shí)的之記為轉(zhuǎn)換后的實(shí)數(shù)。偽碼算法：void Calculate(SqStack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!='#')/讀入后綴表達(dá)式直到“#”符號(hào)為止if(s2i>='0' && s2i<='9' | s2i='.') / 若為數(shù)值和小數(shù)點(diǎn)/則將其聯(lián)合轉(zhuǎn)換為浮點(diǎn)型后進(jìn)棧/數(shù)值轉(zhuǎn)換為實(shí)數(shù)m=0;while(s2i!='

20、; ' && s2i!='.') /讀入的只為數(shù)字m=m*10+(float)(s2i+-'0');/轉(zhuǎn)換為十進(jìn)制的整數(shù)if(s2i='.')/遇到小數(shù)點(diǎn)后j=0;i+;while(s2i!=' ')m=m*10+(float)(s2i+-'0');/轉(zhuǎn)換為十進(jìn)制的整數(shù) j+; /記錄小數(shù)點(diǎn)后的位數(shù)while(j>0) /轉(zhuǎn)換為實(shí)數(shù)m/=10;j-;i+; Push_f(s,m); GetTop_f(s,&m); printf("The result is:%gn&q

21、uot;,m);else /讀入的為運(yùn)算符Pop_f(s,&x);/彈出棧頂元素Pop_f(s,&y);/彈出次頂元素switch(s2i)/讓棧頂和次頂元素與次運(yùn)算符進(jìn)行相應(yīng)的運(yùn)算，運(yùn)算結(jié)果打印并進(jìn)棧case '+':z=y+x;printf("The result is:%gn",z);break;case '-':z=y-x;printf("The result is:%gn",z);break;case '*':z=y*x;printf("The result is:%gn

22、",z);break;case '/':if(x=0) /報(bào)錯(cuò)功能 printf("表達(dá)式出錯(cuò)，除數(shù)為0，無意義n"); exit(1); elsez=y/x;printf("The result is:%gn",z);break;case '':z=1;for(j=1;j<=x;j+) /乘方的運(yùn)算 z=z*y; printf("The result is:%gn",z); Push_f(s,z);i+;6、結(jié)果輸出的偽碼算法：void result(SqStack_f *s)floa

23、t v;GetTop_f(s,&v);printf("The final result is:%gn",v);/以合適的形式輸出結(jié)果，省去不必要的小數(shù)點(diǎn)7、主程序的偽碼算法：void main()SqStack_f stack;char str80,c='Y'while(c='y' | c='Y')/判斷是否繼續(xù)本程序printf("請(qǐng)輸入算術(shù)表達(dá)式本程序支持實(shí)數(shù)的加減乘除乘方運(yùn)算，結(jié)束前請(qǐng)輸入#號(hào)！n"); gets(str);/輸入表達(dá)式 InitStack_f(&stack);/初始化

24、一個(gè)存儲(chǔ)運(yùn)算結(jié)果（實(shí)型）的棧 Translate(str);/調(diào)用“中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式函數(shù)” printf("轉(zhuǎn)化后的后綴表達(dá)式為：n");/檢驗(yàn)后綴表達(dá)式是否轉(zhuǎn)換正確 puts(str);/輸出后綴表達(dá)式 Calculate(&stack,str);/計(jì)算無括號(hào)表達(dá)式的值 result(&stack);/調(diào)用“結(jié)果輸出函數(shù)” printf("你想繼續(xù)嗎？'Y'或'y'為繼續(xù)，其余為退出程序n");/增加程序的連續(xù)輸入功能 c=getchar();getchar();/吞噬掉輸入判斷符后的n8、函數(shù)

25、的調(diào)用關(guān)系圖mainTranslateCalculateresultprecede四、 調(diào)試分析1、 在編程過程中，為了增加程序的實(shí)用性，將程序適用圍擴(kuò)大到了實(shí)數(shù)型，并增加了連續(xù)輸入功能；2、 在編程過程中，為了增加程序的健壯性，在運(yùn)算除法時(shí)，考慮到除數(shù)為“0”時(shí)的報(bào)錯(cuò)和與時(shí)退出；3、 在調(diào)試過程中，最初一下子出來程序就出錯(cuò)，為了方便檢查錯(cuò)誤，故在主函數(shù)中增加了檢查后綴表達(dá)式是否轉(zhuǎn)換正確的函數(shù)，并在每一步計(jì)算都跟蹤結(jié)果是否正確；4、 從程序?qū)嶒?yàn)題的編制過程中容易看出，線性表的廣泛應(yīng)用，特別是順序存儲(chǔ)結(jié)構(gòu)的棧的應(yīng)用。本題中涉與兩元素類型（字符型和浮點(diǎn)型）的棧，由于是面向過程的語言，故只能分別定義

26、。五、 用戶使用說明1、 本程序的運(yùn)行環(huán)境為Windows7旗艦版操作系統(tǒng)，執(zhí)行文件為：算術(shù)表達(dá)式求值.exe；2、 進(jìn)入程序后即顯示提示信息：“請(qǐng)輸入算術(shù)表達(dá)式本程序支持實(shí)數(shù)的加減乘除乘方運(yùn)算，結(jié)束前請(qǐng)輸入#號(hào)！”以等待用戶輸入待求表達(dá)式，直到輸入“#”為止，若用戶輸入的表達(dá)式為一個(gè)空字符串，則顯示ERROR，程序結(jié)束；3、 在用戶正確輸入表達(dá)式后，程序會(huì)自動(dòng)將其轉(zhuǎn)換為后綴表達(dá)式并輸出“轉(zhuǎn)化后的后綴表達(dá)式為：xxxxxxxx”，然后自動(dòng)計(jì)算表達(dá)式的值并輸出中間結(jié)果“The result is：xxxxx”和最終結(jié)果“The final result is:xxxx”；4、 最終結(jié)果輸出后，又

27、有提示信息：“你想繼續(xù)嗎？'Y'或'y'為繼續(xù)，其余為退出程序”，以等待用戶輸入是否繼續(xù)運(yùn)行本程序的命令符，若輸入“y”或“Y”，則程序自動(dòng)再次運(yùn)行，重復(fù)2，3步，若輸入其它，程序結(jié)束。5、 本程序只對(duì)實(shí)數(shù)的加減乘除乘方運(yùn)算進(jìn)行求值，且只對(duì)“（）”這種形式的括號(hào)進(jìn)行識(shí)別，“”或“”都不予以識(shí)別，表達(dá)式輸入完后一定要加“#”表示輸入結(jié)束。六、 測(cè)試結(jié)果1、 正確輸入：12*（3.6/3+42-1）#2、 無定義運(yùn)算：12*（3.6/(22-4)+1）#運(yùn)行界面：3、 錯(cuò)誤輸入：12+s#運(yùn)行界面：以上結(jié)果與自己在進(jìn)行程序概要分析時(shí)的余項(xiàng)結(jié)果一致七、 心得體會(huì)這次實(shí)

28、驗(yàn)設(shè)計(jì)讓我更加了解并更加靈活運(yùn)用大一學(xué)到的C程序設(shè)計(jì)和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)任務(wù)要求不僅要求對(duì)課本知識(shí)有較深刻的了解，同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的思維和動(dòng)手能力和更加了解編程思想和編程技巧。這次實(shí)驗(yàn)設(shè)計(jì)讓我有一個(gè)深刻的體會(huì)，那就是細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過分，往往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)，分號(hào)，引號(hào)，或者數(shù)據(jù)類型上，或者將“i”打成“1”。就像我在寫Calculate（）函數(shù)時(shí)，在進(jìn)行數(shù)值轉(zhuǎn)換時(shí)，一個(gè)“”放錯(cuò)了位置，讓我糾結(jié)了很久。在寫Translate（）函數(shù)時(shí)，switch（s1i）寫成switch（s11），很仔細(xì)的檢查，花了一個(gè)多小時(shí)才發(fā)現(xiàn)次錯(cuò)誤。

29、程序設(shè)計(jì)時(shí)，也不要怕遇到錯(cuò)誤，在實(shí)際操作過程中犯的一些錯(cuò)誤還會(huì)有意外的收獲，感覺課程設(shè)計(jì)很有意思。在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)得到鞏固，達(dá)到課程設(shè)計(jì)的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上機(jī)中應(yīng)更加注意，同時(shí)體會(huì)到C語言具有的語句簡(jiǎn)潔，使用靈活，執(zhí)行效率高等特點(diǎn)。發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù)表達(dá)式有了深刻的理解。最后，感老師在這次課程設(shè)計(jì)的悉心指導(dǎo)，祝老師身體健康，工作順利。參考文獻(xiàn)：1.數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 清華大學(xué) 2.C程序設(shè)計(jì) 譚浩強(qiáng) 清華大學(xué) 3.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）嚴(yán)蔚敏 吳偉民 米寧 清華大學(xué) 4.C程序設(shè)計(jì)學(xué)習(xí)指導(dǎo)與練習(xí)賈伯琪 中國(guó)科學(xué)技術(shù)大學(xué)八、

30、 附錄“表達(dá)式求值”源程序代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define TTACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structfloat *base;float *top;int stacksize;SqStack_f;typedef structchar *base;char *top;int stacksize;SqStack_c;void InitStack_f(SqStack_f *s)s->base=

31、(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void InitStack_c(SqStack_c *s)s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char);if(!s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void GetTop_f(SqS

32、tack_f *s,float *e)if(s->top=s->base)printf("ERROR!n");exit(1);*e=*(s->top-1);void GetTop_c(SqStack_c *s,char *e)if(s->top=s->base)printf("ERROR!n");exit(1);*e=*(s->top-1);void Push_f(SqStack_f *s,float e)if(s->top-s->base>=s->stacksize)s->base=(f

33、loat *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float);if(!s->base)printf("OVERFLOW!n");exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void Push_c(SqStack_c *s,char e)if(s->top-s->base>=s->stacksize)s->base=(ch

34、ar *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base)printf("OVERFLOW!n");exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void Pop_f(SqStack_f *s,float *e)if(s->top=s->base)exit(1);*e=*-s->top;void Pop_c(Sq

35、Stack_c *s,char *e)if(s->top=s->base)exit(1);*e=*-s->top;int precede(char Top_char,char s1_char)int i,pre2;char op2;op0=Top_char;op1=s1_char;for(i=0;i<2;i+)switch(opi)case'(':case')':prei=0;break;case'+':case'-':prei=1;break;case'*':case'/'

36、:prei=2;break;case'':prei=3;break;if(pre0>=pre1)return 1;elsereturn 0;void Translate(char *s1)char s280;SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);Push_c(&Optr,'(');while(s1i!='#')if(s1i>='0' && s1i<='9' | s1i='.')s2j

37、+=s1i;if(s1i+1<'0' | s1i+1>'9') && s1i+1!='.')s2j+=' 'elseswitch(s1i)case'(':Push_c(&Optr,s1i);break;case')':Pop_c(&Optr,&t);while(t!='(')s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),pr

38、ecede(t,s1i)Pop_c(&Optr,&t);s2j+=t;Push_c(&Optr,s1i);i+;Pop_c(&Optr,&t);while(t!='(')s2j+=t;Pop_c(&Optr,&t);for(i=0;i<j;i+)s1i=s2i;s1i='#'s1i+1='0'void Calculate(SqStack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!='#')if(s2i>='0' && s2i&