表達(dá)式求值實(shí)驗(yàn)報(bào)告

1、淮海 工學(xué)院 計(jì)算機(jī)工程學(xué)院課程設(shè)計(jì)報(bào)告設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)選題名稱 ：表達(dá)式求值姓 名：學(xué)號(hào)：_專業(yè)班級(jí)：系 （院）： 計(jì)算機(jī)工程學(xué)院 設(shè)計(jì)時(shí)間：設(shè)計(jì)地點(diǎn)：軟件工程實(shí)驗(yàn)室、教室成績(jī):指導(dǎo)教師評(píng)語(yǔ):簽名：年 月 日1.課程設(shè)計(jì)目的1、訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí) ，編寫(xiě)程序求解指定問(wèn)題。2初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；3提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；4訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過(guò)程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和

2、良好的工作作風(fēng)。2 .課程設(shè)計(jì)任務(wù)與要求：任務(wù)根據(jù)教材數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述耿國(guó)華主編）和參考書(shū)數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）（嚴(yán)蔚 敏、吳偉民主編）選擇課程設(shè)計(jì)題目，要求通過(guò)設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示 、數(shù)據(jù)結(jié) 構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。設(shè)計(jì)題目從任務(wù)書(shū)所列選題表中選取，每班每題不得超過(guò) 2人。學(xué)生自選課題學(xué)生原則上可以結(jié)合個(gè)人愛(ài)好自選課題,要求課題有一定的深度與難度，有一定的算法復(fù)雜性，能夠鞏固數(shù)據(jù)結(jié)構(gòu)課程所學(xué)的知識(shí)。學(xué)生自選課題需在18周前報(bào)課程設(shè)計(jì)指導(dǎo)教師批準(zhǔn)方可生效。要求：1、在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)

3、類型、構(gòu)思算法、通過(guò)設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫(xiě)出完整的分析報(bào) 的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。2、 .設(shè)計(jì)的題目要求達(dá)到一定工作量（300行以上代碼），并具有一定的深度和難度 。3、 程序設(shè)計(jì)語(yǔ)言推薦使用C/C+，程序書(shū)寫(xiě)規(guī)范，源程序需加必要的注釋；4、 每位同學(xué)需提交可獨(dú)立運(yùn)行的程序；5、 每位同學(xué)需獨(dú)立提交設(shè)計(jì)報(bào)告書(shū)（每人一份），要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實(shí)，不 少于10頁(yè)（代碼不算）；6、 課程設(shè)計(jì)實(shí)踐作為培養(yǎng)學(xué)生動(dòng)手能力的一種手段，單獨(dú)考核。3.課程設(shè)計(jì)說(shuō)明書(shū)一需求分析問(wèn)題描述一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operat

4、or)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符 ，界限符有左右括號(hào)和表達(dá)式起始 、結(jié)束符“#”， 如：#(7+15)*( 23-28/4)#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用算符優(yōu)先法”求算 術(shù)表達(dá)式的值?；疽?1) 從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。(2) 顯示輸入序列和棧的變化過(guò)程。二概要設(shè)計(jì)1、設(shè)定操作數(shù)”的棧的抽象數(shù)據(jù)類型定義：ADT SqStack_f數(shù)據(jù)對(duì)象：D= ai a R, N 數(shù)據(jù)關(guān)系：R仁< ai, ai 4 >| ai 4 ,a D ,i=2,，n約定an端為棧頂，ai端為棧底?；?/p>

5、操作：In itStack_f(&S)操作結(jié)果：構(gòu)造一個(gè)空棧SoGetTop_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ù)類型定義：ADT SqStack_c數(shù)據(jù)對(duì)象：D= ai ai 乏屮'_''*''/"'“ 乏數(shù)據(jù)關(guān)系：R仁

6、< ai, ai d >| ai d ,a D ,i=2,，n約定an端為棧頂，ai端為棧底。基本操作：Ini tStack_c(&S)操作結(jié)果：構(gòu)造一個(gè)空棧SoGetTop_c(&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（命令=繼

7、續(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） 無(wú)括號(hào)表示式求值運(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 struct float *base;/存儲(chǔ)實(shí)型數(shù)據(jù)元素的一位數(shù)組float *top;

8、/棧頂指針int stacksize; /棧數(shù)組容量SqStack_f;/有序存儲(chǔ)實(shí)型的順序表類型typedef struct char *base;/存儲(chǔ)字符數(shù)據(jù)元素的一位數(shù)組char *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(SqStac

9、k_c *s,char *e)/若棧s不空，則以e帶值返棧頂元素，否則顯示錯(cuò)誤 ERROR”,并退出程序void Push_f(SqStack_f *s,float e)void Push_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

10、 *s)/構(gòu)造一個(gè)存儲(chǔ)實(shí)型的空棧，預(yù)設(shè)空間為100，分配失敗就退出s->base=( float *)malloc(TTACK_INIT_SIZE* sizeof (float );if(!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)prin tf("ERROR!n ”);exit(1)

11、;*e=*(s->top-1);void Push_f(SqStack_f *s ,float e)/在s的棧頂插入新的棧頂元素 e，若棧的當(dāng)前空間已滿，則追加存儲(chǔ)空間if(s->top-s->base>=s->stacksize)sizeof (float );s->base=( float *)realloc(s->base,(s->stacksize+STACKINCREMENT)* if(!s->base)prin tf("OVERFLOW!n");exit(1);s->top=s->base+s-&

12、gt;stacksize; s->stacksize+=STACKINCREMENT;*s->top+=e;void Pop_f(SqStack_f *s, float *e)/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序if(s->top=s->base)exit(1);*e=*_s_>top;3、判斷運(yùn)算符優(yōu)先級(jí)的算法：算符間的優(yōu)先關(guān)系如下+-*/()#+>=<<<<>>->>=<<<>>*>>>=><>>/>&g

13、t;>>=<>>(<<<<<=)>>>>>>#<<<<<=偽碼算法：int precede (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=T op_char; /棧頂?shù)倪\(yùn)算符賦給op0op1=s1_char; / 新讀入的運(yùn)算符賦給 op1for (i=0;i<2;i+)s

14、witch (opi)case'(': case ')':prei=0; break ; / 將括號(hào)的優(yōu)先級(jí)設(shè)為0case'+': case'-':prei=1; break ; / 將 + - 運(yùn)算符的優(yōu)先級(jí)設(shè)為 1case '*': case '/':prei=2; break ; / 將* / 運(yùn)算符的優(yōu)先級(jí)設(shè)為2case 'A':prei=3;break ;/將A運(yùn)算符的優(yōu)先級(jí)設(shè)為3if (pre0>=pre1)/棧頂元素優(yōu)先級(jí)高返回1return 1;else4、中綴

15、表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法：算法過(guò)程描述：1) 首先將左括號(hào)壓進(jìn)棧，作為棧底元素；2) 從左而右對(duì)算數(shù)表達(dá)式進(jìn)行掃描，每次讀入一個(gè)字符s1i；3) 若遇到數(shù)字或小數(shù)點(diǎn)，則立即寫(xiě)入s2i，若遇算數(shù)運(yùn)算符，將“”空格)寫(xiě)入s2i；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 Tran

16、slate( char *s1) /中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式char s280;SqStack_c Optr;int i=0,j=0;cha r t;InitStack_c(&Optr);初始化一個(gè)存儲(chǔ)字符型的空棧，便于存儲(chǔ)運(yùn)算符Push_c(&Optr,'(');首先將左括號(hào)壓進(jìn)棧，作為棧底元素while (s1i!='#') /當(dāng)掃描到的不是#”，即表達(dá)式串沒(méi)結(jié)束時(shí)if (s1i>='0' && s1i<=9 | s1i='.') /若果是數(shù)字或小數(shù)點(diǎn)則將其輸出給s2is2j+=s

17、1i;if (s1i+1<'0' | s1i+1>'9') && s1i+1!='.')s2j+=''elseswitch( s1i) /掃描到的是運(yùn)算符case '(':Push_c(&0ptr,s1i); break;/ 遇到左括號(hào)("則壓棧case ')':Pop_c(&Optr,&t); /若遇到右括號(hào)“)”則將棧頂元素輸出到s2iwhile (t!='(') /直到棧頂元素為“(”然后相互抵消s2 j+=t;Po

18、p_c(&Optr, &t);break ;default :while (GetTop_c(&Optr,&t),precede(t,s1i)/遇到算數(shù)運(yùn)算符則比較優(yōu)先級(jí)Pop_c(&Optr,&t);棧頂元素優(yōu)先級(jí)高，則彈出到s2is2j+=t;Push_c(&0ptr,s1i);棧頂元素優(yōu)先級(jí)低，直接壓棧Pop_c(&Optr, &t);while (t!='(')表達(dá)式串已結(jié)束，棧中的運(yùn)算符全部輸出到s2i,并刪除棧頂元素s2j+=t;Pop_c(&Optr, &t);for (i=0

19、;i<j;i+) / 將 s2 復(fù)制給 s1s1i=s2i;s1i= '#'s1i+1='0'為了方便打印后綴表達(dá)式，在字符串結(jié)尾加0 '5、表示式求值運(yùn)算的算法：算法描述：1) 讀入無(wú)括號(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è)變

20、量m 上;2) 若繼續(xù)為數(shù)字，也將其減去'0'的ASCII碼后就得到該數(shù)的數(shù)值，并將其值加上已存的m*10 后的值再存于m ;3) 重復(fù)2)步驟直到遇到小數(shù)點(diǎn)，從小數(shù)點(diǎn)后的數(shù)開(kāi)始，在重復(fù)2)步驟的通知，也記下小數(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;in t i=0,j=0;while (s2i!='#')讀入后綴表達(dá)式直到#”符號(hào)為止if(s2i>=

21、9;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!=' ' && 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)后的位

22、數(shù)while (j>0) /轉(zhuǎn)換為實(shí)數(shù)m/=10;j-；i+；Push_f(s,m);GetTop_f(s,&m);prin tf("The result is:%gn",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;p

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

24、d result(SqStack_f *s)float 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á)式Ini

25、tStack_f(&stack); 初始化一個(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ì)算無(wú)括號(hào)表達(dá)式的值result(&stack);/調(diào)用結(jié)果輸出函數(shù)”printf("你想繼續(xù)嗎？ 'Y'或'y'為繼續(xù)，其余為退出程序n”);/增加程序的連續(xù)輸入功能c=getchar();getchar();吞噬掉輸入判斷符后的n &#

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

27、，執(zhí)行文件為：算術(shù)表達(dá)式求值.exe ；2、 進(jìn)入程序后即顯示提示信息：請(qǐng)輸入算術(shù)表達(dá)式，以'#'結(jié)束”以等待用戶輸入待求表達(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é)果輸出后，又有提示信息：你想繼續(xù)嗎？ 'Y'或'y'為繼續(xù)，

28、其余為退出程序”，以等待 用戶輸入是否繼續(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è)試成果1、程序主界面2、輸入正確的表達(dá)式輸入10* (4.8/4+3人2-5 ) #,會(huì)打印出該式的后綴表達(dá)式，并求出最終結(jié)果當(dāng)進(jìn)行完一次運(yùn)算后，輸入Y或y會(huì)繼續(xù)進(jìn)行下一次運(yùn)算3、輸入除數(shù)為0的表達(dá)式輸入10* (2.7/ (3A2-9 ) -1 ) #后，會(huì)提示除數(shù)為0,無(wú)意義本窿按

29、讎毒歸鳩除乘方運(yùn)算 術(shù)表達(dá)式.以F'結(jié)耒7 3 2 result yezult result result result result result resultISISisisISisis-/I -*lt102_73390靈達(dá)式出錯(cuò)，除數(shù)為無(wú)意義Ji*ess anu key to continueIS4、輸入錯(cuò)誤的格式輸入15+a#后，會(huì)提示ERROR并退出程序本程庫(kù)支舊黯空鶴二 _ 請(qǐng)端入尊術(shù)表達(dá)式，以結(jié)東乘除乘方運(yùn)算-ERPOR*七附錄(源程序清單)#in clude<stdio.h>#in clude<stdlib.h>#in clude<mall

30、oc.h>#define TTACK_INIT_SIZE 100/初始分配最大空間量#define STACKINCREMENT 10/ (默認(rèn))增補(bǔ)空間量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 *top;/棧頂指針int stacksize; / 棧數(shù)組容量SqStack_c; /有序存儲(chǔ)字符型的順序表類型void In itStack_

31、f(SqStack_f *s)/構(gòu)造一個(gè)存儲(chǔ)實(shí)型的空棧，預(yù)設(shè)空間為100，分配失敗就退出s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float); if(!s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void In itStack_c(SqStack_c *s)/構(gòu)造一個(gè)存儲(chǔ)字符型的空棧，預(yù)設(shè)空間為100,分配失敗就退出s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char);if(!s-

32、>base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;void GetT op_f(SqStack_f *s,float *e)/若棧s不空，則以e帶值返棧頂元素，否則顯示錯(cuò)誤"ERROR",并退出程序if(s->top=s->base)prin tf("ERROR!n");exit(1);*e=*(s->top-1); void GetT op_c(SqStack_c *s,char *e)/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程

33、序if(s->top=s->base)prin tf("ERROR!n");exit(1);*e=s->top+=e;(s->top-1);void Push_f(SqStack_f *s,float e)/在s的棧頂插入新的棧頂元素e，若棧的當(dāng)前空間已滿，則追加存儲(chǔ)空間if(s->top-s->base>=s->stacksize)s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float);if(!s->ba

34、se) prin tf("OVERFLOW!n ”); exit(1);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;void Push_c(SqStack_c *s,char e)/在s的棧頂插入新的棧頂元素e,若棧的當(dāng)前空間已滿，則追加存儲(chǔ)空間if(s->top-s->base>=s->stacksize)s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(cha

35、r);if(!s->base)printf("棧滿，溢出 n”); exit(1); s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT;*s->top+=e; void Pop_f(SqStack_f *s,float *e)/若棧s不空，則刪除棧s的棧頂元素，用e帶值返回，否則退出程序if(s->top=s->base)exit(1);*e=*-s->top;void Pop_c(SqStack_c *s,char *e)/若棧s不空，則刪除棧s的棧頂元素，用e帶

36、值返回，否則退出程序if(s->top=s->base)exit(1);*e=*_s_>top; int precede(char T op_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=T op_char; /棧頂?shù)倪\(yùn)算符賦給 op1=s1_char; / 新讀入的運(yùn)算符賦給 for(i=0;i<2;i+)switch(opi)case'A':prei=3;break;op0op1將括

37、號(hào)的優(yōu)先級(jí)設(shè)為0將+ -運(yùn)算符的優(yōu)先級(jí)設(shè)為1將* /運(yùn)算符的優(yōu)先級(jí)設(shè)為2/將A運(yùn)算符的優(yōu)先級(jí)設(shè)為 3case'(':case')':prei=0;break; / case'+':case'-':prei=1;break; / case'*':case'/':prei=2;break; /if(pre0>=pre1)/棧頂元素優(yōu)先級(jí)高返回1return 1;elsereturn 0;/否則返回0void Tran slate(char *s1) /中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式char s280;

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

39、1<'0' | s1i+1>'9') && s1i+1!='.')s2j+=''elseswitch(s1i) /掃描到的是運(yùn)算符case'(':Push_c(&0ptr,s1i);break;遇到左括號(hào)"("則壓棧case')':Pop_c(&Optr,&t); /若遇到右括號(hào)”)"，則將棧頂元素輸出到s2iwhile(t!='(') /直到棧頂元素為"(”，然后相互抵消s2j+=t;Pop

40、_c(&Optr, &t);break;default:while(GetTop_c(&Optr, &t),precede(t,s1i)/遇到算數(shù)運(yùn)算符則比較優(yōu)先級(jí)Pop_c(&Optr,&t); 棧頂元素優(yōu)先級(jí)高，則彈出到s2is2 j+=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

41、=0;i<j;i+) / 將 s2 復(fù)制給 sis1i=s2i;s1i= '#'s1i+1='0'為了方便打印后綴表達(dá)式，在字符串結(jié)尾加'0'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)

42、換為實(shí)數(shù)m=0;while(s2i!=' ' && s2i!='.') /讀入的只為數(shù)字m=m*10+(float)(s2i+-'0');轉(zhuǎn)換為十進(jìn)制的整數(shù)if(s2i='.') 遇到小數(shù)點(diǎn)后j=O；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);prin tf("

43、The result is:%gn",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;pri ntf("The result is:%gn",z);break;case '-':z=y-x;pri ntf("The result is:%gn",z);break;case '*':z=y* x;pri ntf("The result is:%gn",z);break;case 7':if(x=0)/報(bào)錯(cuò)功能printf("表達(dá)式出錯(cuò)，除數(shù)為O',無(wú)意義n"); exit(1);elsez=y/x;prin tf("The result is:%gn",z);break;case 小':z=1;for(j=1;j<=x;j+)/乘方的運(yùn)算z=z*y;prin tf("The r