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

1、 .軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 表達(dá)式計(jì)算器 系 別： 通信工程 年 級： 班 級： 學(xué)生學(xué)號： 學(xué)生： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 題目 簡易計(jì)算表達(dá)式的演示題目要求要求：實(shí)現(xiàn)基本表達(dá)式計(jì)算的功能輸入：數(shù)學(xué)表達(dá)式，表達(dá)式由整數(shù)和“+”、 “-”、“×”、“/”、“（”、“）”組成輸出：表達(dá)式的值基本操作：鍵入表達(dá)式，開始計(jì)算，計(jì)算過程和結(jié)果記錄在文檔中難點(diǎn)：括號的處理、乘除的優(yōu)先級高于加減1前言在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號組成。由于不同的運(yùn)算符具有不同的優(yōu)先級，又要考慮括號，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)行。因而在程序設(shè)計(jì)時，借助棧實(shí)現(xiàn)。算法輸入：一

2、個算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號組成（以字符串形式輸入）。為簡化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為+、-*、/、=，用#表示結(jié)束。算法輸出：表達(dá)式運(yùn)算結(jié)果。算法要點(diǎn)：設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。在讀入表達(dá)式的字符序列的同時，完成運(yùn)算符和運(yùn)算數(shù)的識別處理，以與相應(yīng)運(yùn)算。2概要設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)任何一個表達(dá)式都是由操作符，運(yùn)算符和界限符組成的。我們分別用順序棧來寄存表達(dá)式的操作數(shù)和運(yùn)算符。棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表。順序棧的存儲結(jié)構(gòu)是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針top指示棧頂元素在順序棧中的位置，base為棧底

3、指針，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉?biāo)記，每當(dāng)插入新的棧頂元素時，指針top增1，刪除棧頂元素時，指針top減1。2.2 算法設(shè)計(jì)為了實(shí)現(xiàn)算符優(yōu)先算法。可以使用兩個工作棧。一個稱為OPTR，用以寄存運(yùn)算符，另一個稱做OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果。1.首先置操作數(shù)棧為空棧，表達(dá)式起始符”#”為運(yùn)算符棧的棧底元素；2.依次讀入表達(dá)式，若是操作符即進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為”#”）。2.3 ADT描述ADT Stack數(shù)據(jù)對象：D= |ElemSet,

4、i=1,2,，n, n0數(shù)據(jù)對象：R1=<>|,i=2,，n約定端為棧頂，端為棧底?；静僮鳎?InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧S。 GetTop(S) 初始條件：棧S已存在。 操作結(jié)果：用P返回S的棧頂元素。 Push(&S，ch) 初始條件：棧S已存在。 操作結(jié)果：插入元素ch為新的棧頂元素。 Pop(&S) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運(yùn)算符，運(yùn)算符即返回1。 Precede(c1, c2) 初始條件：c1,c2為運(yùn)算符。操作結(jié)果：判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Opera

5、te(a,op,b)初始條件：a,b為整數(shù)，op為運(yùn)算符。操作結(jié)果：a與b進(jìn)行運(yùn)算，op為運(yùn)算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達(dá)式合法。操作結(jié)果：返回表達(dá)式的最終結(jié)果。ADT Stack2.4 功能模塊分析1.棧的基本功能。InitStack(Stack *s) 和InitStack2(Stack2 *s)分別構(gòu)造運(yùn)算符棧與構(gòu)造操作數(shù)棧，Push(Stack *s,char ch) 運(yùn)算符棧插入ch為新的棧頂元素，Push2(Stack2 *s,int ch) 操作數(shù)棧插入ch為新的棧頂元素，Pop(Stack *s) 刪除運(yùn)算符棧s的

6、棧頂元素，用p返回其值，Pop2(Stack2 *s)刪除操作數(shù)棧s的棧頂元素，用p返回其值，GetTop(Stack s)用p返回運(yùn)算符棧s的棧頂元素，GetTop2(Stack2 s) 用p返回操作數(shù)棧s的棧頂元素。2.其它功能分析。 (1)In(char ch) 判斷字符是否是運(yùn)算符功能，運(yùn)算符即返回1，該功能只需簡單的一條語句即可實(shí)現(xiàn)，return(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='#')。 (2) Precede(c

7、har c1,char c2) 判斷運(yùn)算符優(yōu)先權(quán)功能，該函數(shù)判斷運(yùn)算符c1,c2的優(yōu)先權(quán)，具體優(yōu)先關(guān)系參照表1。 (3) Operate(int a,char op,int b)操作數(shù)用對應(yīng)的運(yùn)算符進(jìn)行運(yùn)算功能。運(yùn)算結(jié)果直接返回。(4) num(int n) 求操作數(shù)的長度功能，需要用itoa函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函數(shù)可求字符長度。(5) EvalExpr()主要操作函數(shù)運(yùn)算功能。分析詳細(xì)見“3.詳細(xì)設(shè)計(jì)3.2”。3詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計(jì) 因?yàn)楸磉_(dá)式是由操作符，運(yùn)算符和界限符組成的。如果只用一個char類型棧，不能滿足2位以上的整數(shù)，所以還需要定義一個int類型的

8、棧用來寄存操作數(shù)。/* 定義字符類型棧 */struct stacklifei1 /數(shù)字棧的定義double *base;double *top;s1;/struct stacklifei2 /運(yùn)算符棧的定義char *base;char *top;s2;3.2 計(jì)算功能的實(shí)現(xiàn)void jisuan() / 該函數(shù)對數(shù)字棧的前兩個棧頂 /元素與符號棧的棧頂元素完成一次運(yùn)算操作double a,b;b=*(s1.top-1); s1.top-;if(s1.top=s1.base)error=1;return ; a=*(s1.top-1); switch(*(s2.top-1)case '

9、;+':a=a+b;break;case '-':a=a-b;break;case '*':a=a*b;break;case '/':if(b=0)error=2;s2.top=s2.base;return ;/除數(shù)不為0else a=a/b;break;default :error=1;fprintf(file,"%lf %c %lf= %lfn",*(s1.top-1),*(s2.top-1),b,a);*(s1.top-1)=a; /將運(yùn)算結(jié)果入棧s2.top-; return ;3.3函數(shù)表達(dá)式求值功能的實(shí)現(xiàn)v

10、oid qiuzhi(char *cr) 該函數(shù)完成對表達(dá)式的處理int i=0,k,h,flag,fuhao=0;double sum,j;s1.base=s1.top=shuzhi;s2.base=s2.top=fuha; *(s2.top)='#' s2.top+;while(s2.top!=s2.base)sum=0;flag=0;k=10;j=1;h=1;while(cri>='0'&&cri<='9'|cri='.')/若當(dāng)前的字符是數(shù)字，就將char型的數(shù)據(jù)轉(zhuǎn)換為double型if(cri

11、='.')if(cri-1<'0'|cri-1>'9'|i=0|cri+1<'0'|cri+1>'9')error=1;break;elsek=1;h=10;elseflag=1;j=j*h;sum=sum*k+(cri-48)/j; i+;3.4對函數(shù)表達(dá)式每個字符的操作switch(cri)case '-':if(cri-1='('|i=0)fuhao=1;i+;break;/判斷是不是負(fù)號，若不是則進(jìn)行與加號一樣的操作/當(dāng)'-'出現(xiàn)在表達(dá)

12、式第一位或是'('后第一位,則應(yīng)將其判為負(fù)號case '+': /加、減號的優(yōu)先級只比'('和'='高，若棧頂元素為這兩者之一/就將其入棧，否則執(zhí)行運(yùn)算操作if(*(s2.top-1)='('|*(s2.top-1)='#')*(s2.top)=cri;s2.top+;i+;else jisuan();break;case '*':case '/':/乘、除號的優(yōu)先級只比'*'、'/'和''低，若棧頂元素為這三者之一/就

13、執(zhí)行運(yùn)算操作，否則將其入棧if(*(s2.top-1)='*'|*(s2.top-1)='/')jisuan(); else *(s2.top)=cri;s2.top+;i+;break;case '(': *(s2.top)=cri; s2.top+;i+;break;/未入棧時'('的優(yōu)先級最高，所以它一定要入棧/但一入棧其優(yōu)先級就應(yīng)降為最低case ')':/注意：由于'()'運(yùn)算優(yōu)先級最高故我直接進(jìn)行運(yùn)算，/直到棧頂元素為'('后將'('出棧，故符號棧中一定沒

14、有')'，/這也是我進(jìn)行以上優(yōu)先級判斷的前提if(*(s2.top-1)='(')s2.top-;i+;else jisuan();break;case '=':/表達(dá)式結(jié)束，若符號棧棧頂元素不為'#'，進(jìn)行運(yùn)算/否則退棧，結(jié)束if(*(s2.top-1)='#')s2.top-;else jisuan();break;default :i+; /清除空格與未定義符號3.5主菜單頁面的實(shí)現(xiàn)void main()char cr60;char c='a'file=fopen(outfile,"

15、w+");/使用提示printf("*n");printf("*斐計(jì)算器*n");printf("四則簡易計(jì)算器nn");printf("輸入表達(dá)式例如 2+4= nn");printf("最后按 # 鍵 則會退出保存nn");printf("使用nn");printf("-n");printf("*n");/循環(huán)輸入表達(dá)式，按'#'鍵退出while(c!='#')error=0;printf(

16、"輸入表達(dá)式:n");gets(cr);fprintf(file,"表達(dá)式：%sn",cr);qiuzhi(cr);printf("任意鍵繼續(xù)，按 # 鍵退出:n");c=getch();fclose(file);附加一 算符間的優(yōu)先關(guān)系如下：+-*/()=#+><<<<>>>->><<<>>>*>>>><>>>/>>>><>>>(<<

17、;<<<=>>)>>>>=>>>=<<<<<<=<#<<<<<<>=4軟件測試1.運(yùn)行成功后界面。2.輸入正確的表達(dá)式后。3.更改表達(dá)式，帶括號輸出 5心得體會這次課程設(shè)計(jì)讓我再一次加了解大一學(xué)到的C和這個學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。課設(shè)題目要求不僅要求對課本知識有較深刻的了解，同時要求程序設(shè)計(jì)者有較強(qiáng)的思維和動手能力和更加了解編程思想和編程技巧。這次課程設(shè)計(jì)讓我有一個深刻的體會，那就是細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過分，往往檢查

18、了半天發(fā)現(xiàn)錯誤發(fā)生在某個括號，分號，引號，或者數(shù)據(jù)類型上。就一點(diǎn)小小的錯誤也耽誤了我?guī)资昼?，所以說細(xì)節(jié)很重要。 程序設(shè)計(jì)時，也不要怕遇到錯誤，在實(shí)際操作過程中犯的一些錯誤還會有意外的收獲，感覺課程設(shè)計(jì)很有意思。在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知識得到鞏固，達(dá)到課程設(shè)計(jì)的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上機(jī)中應(yīng)更加注意，同時體會到C語言具有的語句簡潔，使用靈活，執(zhí)行效率高等特點(diǎn)。發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù)表達(dá)式有了深刻的理解。 最后，感老師在這門數(shù)據(jù)結(jié)構(gòu)課程的悉心指導(dǎo)，祝老師和助教身體健康，萬事如意！參考文獻(xiàn)1.數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 清華大學(xué)2.C程序設(shè)計(jì) 譚浩強(qiáng) 清華

19、大學(xué)附 錄程序源代碼：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<conio.h> struct stacklifei1 /數(shù)字棧的定義double *base;double *top;s1;struct stacklifei2 /運(yùn)算符棧的定義char *base;char *top;s2;double shuzhi40; /數(shù)字棧char fuha40; /符號棧int error; /出錯標(biāo)識符FILE *file;char outfile30="life

20、ijisuanqi.txt"void jisuan() / 該函數(shù)對數(shù)字棧的前兩個棧頂 /元素與符號棧的棧頂元素完成一次運(yùn)算操作double a,b;b=*(s1.top-1); /取數(shù)字棧棧頂元素s1.top-;if(s1.top=s1.base)error=1;return ; /若?？眨鲥ea=*(s1.top-1); /取數(shù)字棧棧頂元素switch(*(s2.top-1)case '+':a=a+b;break;case '-':a=a-b;break;case '*':a=a*b;break;case '/':

21、if(b=0)error=2;s2.top=s2.base;return ;/除數(shù)不為0else a=a/b;break;default :error=1;fprintf(file,"%lf %c %lf= %lfn",*(s1.top-1),*(s2.top-1),b,a);*(s1.top-1)=a; /將運(yùn)算結(jié)果入棧s2.top-; /運(yùn)算符退棧return ;void qiuzhi(char *cr)/qiuzhi()；該函數(shù)完成對表達(dá)式的處理int i=0,k,h,flag,fuhao=0;double sum,j;s1.base=s1.top=shuzhi;s2

22、.base=s2.top=fuha; /數(shù)字棧與符號棧初始化*(s2.top)='#' /將'#'入棧，方便循環(huán)s2.top+;while(s2.top!=s2.base)sum=0;flag=0;k=10;j=1;h=1;while(cri>='0'&&cri<='9'|cri='.')/若當(dāng)前的字符是數(shù)字，就將char型的數(shù)據(jù)轉(zhuǎn)換為double型if(cri='.')if(cri-1<'0'|cri-1>'9'|i=0|cr

23、i+1<'0'|cri+1>'9')/判斷小數(shù)點(diǎn)是否出錯error=1;break;elsek=1;h=10;elseflag=1;j=j*h;sum=sum*k+(cri-48)/j; i+;if(flag) /flag不為0表明有數(shù)據(jù)需要入棧if(fuhao)sum=-sum;fuhao=0;/fuhao是個標(biāo)志記號，值不為0表明剛才轉(zhuǎn)換的值為負(fù)數(shù)*(s1.top)=sum;s1.top+;else switch(cri)case '-':if(cri-1='('|i=0)fuhao=1;i+;break;/判斷是

24、不是負(fù)號，若不是則進(jìn)行與加號一樣的操作/當(dāng)'-'出現(xiàn)在表達(dá)式第一位或是'('后第一位,則應(yīng)將其判為負(fù)號case '+': /加、減號的優(yōu)先級只比'('和'='高，若棧頂元素為這兩者之一/就將其入棧，否則執(zhí)行運(yùn)算操作if(*(s2.top-1)='('|*(s2.top-1)='#')*(s2.top)=cri;s2.top+;i+;else jisuan();break;case '*':case '/':/乘、除號的優(yōu)先級只比'*'、

25、'/'和''低，若棧頂元素為這三者之一/就執(zhí)行運(yùn)算操作，否則將其入棧if(*(s2.top-1)='*'|*(s2.top-1)='/')jisuan(); else *(s2.top)=cri;s2.top+;i+;break;case '(': *(s2.top)=cri; s2.top+;i+;break;/未入棧時'('的優(yōu)先級最高，所以它一定要入棧/但一入棧其優(yōu)先級就應(yīng)降為最低case ')':/注意：由于'()'運(yùn)算優(yōu)先級最高故我直接進(jìn)行運(yùn)算，/直到棧頂元

26、素為'('后將'('出棧，故符號棧中一定沒有')'，/這也是我進(jìn)行以上優(yōu)先級判斷的前提if(*(s2.top-1)='(')s2.top-;i+;else jisuan();break;case '=':/表達(dá)式結(jié)束，若符號棧棧頂元素不為'#'，進(jìn)行運(yùn)算/否則退棧，結(jié)束if(*(s2.top-1)='#')s2.top-;else jisuan();break;default :i+; /清除空格與未定義符號if(error)break;if(error|s1.top-1!=s1.base)/若運(yùn)行出錯或是數(shù)字棧中的元素不是一個，就進(jìn)行出錯提醒if(error=2)printf("除數(shù)不能為0！n");fprintf(file,"%sn","除數(shù)不能為0！");else printf("表達(dá)式錯誤！n");fprintf(file,"%sn","表達(dá)式錯誤！");else /結(jié)果輸出，輸出小數(shù)點(diǎn)后六位，fprintf(file,"結(jié)束n");printf("%.6lfn",*(s1.ba