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

1、本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 表達(dá)式計(jì)算器系 別： 通信工程年 級(jí)：班 級(jí)：學(xué)生學(xué)號(hào)：學(xué)生姓名：數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告題目 簡(jiǎn)易計(jì)算表達(dá)式的演示【題目要求】要求：實(shí)現(xiàn)基本表達(dá)式計(jì)算的功能 輸入：數(shù)學(xué)表達(dá)式，表達(dá)式由整數(shù)和“ +”、 “-”、“”、“/”、“（”、“）”組成 輸出：表達(dá)式的值 基本操作：鍵入表達(dá)式，開(kāi)始計(jì)算，計(jì)算過(guò)程和結(jié)果記錄在文檔中 難點(diǎn)：括號(hào)的處理、乘除的優(yōu)先級(jí)高于加減本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！1前言 在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號(hào)組成。由于不同的運(yùn)算符具有不 同的優(yōu)先級(jí)，又要考慮括號(hào)，因此，算術(shù)表達(dá)式的求值不

2、可能嚴(yán)格地從左到右進(jìn)行。因而在 程序設(shè)計(jì)時(shí)，借助棧實(shí)現(xiàn)。算法輸入：一個(gè)算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號(hào)組成（以字符串形式輸入） 。 為簡(jiǎn)化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為 +、-* 、/、=，用 #表示結(jié)束。算法輸出：表達(dá)式運(yùn)算結(jié)果。 算法要點(diǎn)：設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。在讀入表達(dá)式的字符序列 的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理，以及相應(yīng)運(yùn)算。2概要設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 任何一個(gè)表達(dá)式都是由操作符，運(yùn)算符和界限符組成的。我們分別用順序棧來(lái)寄存表達(dá) 式的操作數(shù)和運(yùn)算符。棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表。順序棧的存儲(chǔ) 結(jié)構(gòu)是利用一組連續(xù)的存儲(chǔ)單元依次存

3、放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針 top 指示 棧頂元素在順序棧中的位置， base為棧底指針，在順序棧中，它始終指向棧底，即 top=base 可作為?？盏臉?biāo)記，每當(dāng)插入新的棧頂元素時(shí)，指針 top 增 1，刪除棧頂元素時(shí)，指針 top 減 1 。2.2 算法設(shè)計(jì) 為了實(shí)現(xiàn)算符優(yōu)先算法?？梢允褂脙蓚€(gè)工作棧。一個(gè)稱為OPTR，用以寄存運(yùn)算符，另一個(gè)稱做 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)的操作，直至整個(gè)表達(dá)

4、式求值完畢（即 OPTR 棧的棧頂元素和當(dāng)前讀入 的字符均為” #”）。2.3 ADT 描述ADT Stack數(shù)據(jù)對(duì)象： D= ai |ai ElemSet,i=1,2,， n, n0數(shù)據(jù)對(duì)象： R1=|ai 1,ai D ,i=2,， n本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！ 約定 an端為棧頂， ai 端為棧底。基本操作：InitStack(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧 S。GetTop(S)初始條件：棧 S 已存在。操作結(jié)果：用 P 返回 S的棧頂元素。Push(&S，ch)初始條件：棧 S 已存在。 操作結(jié)果：插入元素 ch 為新的棧頂元素。Pop(&S)初始條件：棧 S 已存在。 操

5、作結(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)高的。 Operate(a,op,b) 初始條件： a,b為整數(shù)， op為運(yùn)算符。 操作結(jié)果： a 與 b 進(jìn)行運(yùn)算， op 為運(yùn)算符，返回其值。 num(n) 操作結(jié)果：返回操作數(shù)的長(zhǎng)度。EvalExpr() 初始條件：輸入表達(dá)式合法。 操作結(jié)果：返回表達(dá)式的最終結(jié)果。 ADT Stack2.4 功能模塊分析 1.棧的基本功能。InitStack(Stack *s) 和 InitStack2(S

6、tack2 *s)分別構(gòu)造運(yùn)算符棧與構(gòu)造操作數(shù)棧， 本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！Push(Stack *s,char ch) 運(yùn)算符棧插入 ch 為新的棧頂元素， Push2(Stack2 *s,int ch) 操作數(shù)棧插入 ch 為新的棧頂元素， Pop(Stack *s) 刪除運(yùn)算符棧 s的棧頂元素，用 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

7、) 判斷字符是否是運(yùn)算符功能， 運(yùn)算符即返回 1，該功能只需簡(jiǎn)單的一 條語(yǔ)句即可實(shí)現(xiàn)， return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#)。(2) Precede(char 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ù)用對(duì)應(yīng)的運(yùn)算符進(jìn)行運(yùn)算功能。運(yùn)算結(jié)果直接 返回。(4) num(int n) 求操作數(shù)的長(zhǎng)度功能， 需要用 itoa 函數(shù)把 int 型轉(zhuǎn)換成字符串型， strlen 函 數(shù)可求字符長(zhǎng)度。(5) EvalExp

8、r()主要操作函數(shù)運(yùn)算功能。分析詳細(xì)見(jiàn)“ 3.詳細(xì)設(shè)計(jì) 3.2”。3詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 因?yàn)楸磉_(dá)式是由操作符， 運(yùn)算符和界限符組成的。 如果只用一個(gè) char 類型棧，不能 滿足 2位以上的整數(shù)，所以還需要定義一個(gè) int 類型的棧用來(lái)寄存操作數(shù)。/* 定義字符類型棧 */struct stacklifei1/ 數(shù)字棧的定義double *base;double *top;s1;/struct stacklifei2 / 運(yùn)算符棧的定義char *base; char *top;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！s2;3.2 計(jì)算功能的實(shí)現(xiàn)void jisuan() / 該函數(shù)

9、對(duì)數(shù)字棧的前兩個(gè)棧頂/元素與符號(hào)棧的棧頂元素完成一次運(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 +: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= %lf

10、n,*(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) void qiuzhi(char *cr)本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！ 該函數(shù)完成對(duì)表達(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&c

11、ri=9|cri=.)/若當(dāng)前的字符是數(shù)字，就將 char型的數(shù)據(jù)轉(zhuǎn)換為 double 型if(cri=.)if(cri-19|i=0|cri+19)error=1;break;elsek=1;h=10;elseflag=1;j=j*h;sum=sum*k+(cri-48)/j; i+;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！3.4 對(duì)函數(shù)表達(dá)式每個(gè)字符的操作 switch(cri)case -:if(cri-1=(|i=0)fuhao=1;i+;break;/判斷是不是負(fù)號(hào)，若不是則進(jìn)行與加號(hào)相同的操作/當(dāng)-出現(xiàn)在表達(dá)式第一位或是 (后第一位 ,則應(yīng)將其判為負(fù)號(hào) case +:/加、減號(hào)的優(yōu)先級(jí)

12、只比 (和 =高，若棧頂元素為這兩者之一 /就將其入棧，否則執(zhí)行運(yùn)算操作 if(*(s2.top-1)=(|*(s2.top-1)=#)*(s2.top)=cri;s2.top+;i+;else jisuan();break;case /:/乘、除號(hào)的優(yōu)先級(jí)只比 * 、/和低，若棧頂元素為這三者之一 /就執(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;/未入棧時(shí) (的優(yōu)先級(jí)最高，所以它一

13、定要入棧 /但一入棧其優(yōu)先級(jí)就應(yīng)降為最低本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！case ):/注意：由于 ()運(yùn)算優(yōu)先級(jí)最高故我直接進(jìn)行運(yùn)算，/直到棧頂元素為 (后將 (出棧，故符號(hào)棧中一定沒(méi)有 )， /這也是我進(jìn)行以上優(yōu)先級(jí)判斷的前提if(*(s2.top-1)=()s2.top-;i+;else jisuan();break;case =:/表達(dá)式結(jié)束，若符號(hào)棧棧頂元素不為 #，進(jìn)行運(yùn)算/否則退棧，結(jié)束if(*(s2.top-1)=#)s2.top-;else jisuan();break;default :i+; / 清除空格及未定義符號(hào)3.5 主菜單頁(yè)面的實(shí)現(xiàn)void main()cha

14、r cr60;char c=a;file=fopen(outfile,w+);/使用提示printf(*n);李斐計(jì)本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！printf（ 四則簡(jiǎn)易計(jì)算器 nn）;printf（ 輸入表達(dá)式例如 2+4= nn）; printf（最后按 # 鍵 則會(huì)退出保存 nn）; printf（謝謝使用 nn）;n);printf(printf( *n);/循環(huán)輸入表達(dá)式，按 #鍵退出 while(c!=#)error=0;printf( 輸入表達(dá)式 :n);gets(cr);fprintf(file, 表達(dá)式： %sn,cr);qiuzhi(cr);printf( 任意鍵繼續(xù)

15、，按 # 鍵退出 :n);c=getch();fclose(file);附加一】 算符間的優(yōu)先關(guān)系如下：+-*/()=#+-*/()=本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！#=4軟件測(cè)試1.運(yùn)行成功后界面。2.輸入正確的表達(dá)式后 。3. 更改表達(dá)式，帶括號(hào)輸出5心得體會(huì)這次課程設(shè)計(jì)讓我再一次加了解大一學(xué)到的 C 和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。 課設(shè)題目要 求不僅要求對(duì)課本知識(shí)有較深刻的了解， 同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的思維和動(dòng)手能力和更 加了解編程思想和編程技巧。這次課程設(shè)計(jì)讓我有一個(gè)深刻的體會(huì)，那就是細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如 何的嚴(yán)謹(jǐn)都不過(guò)分，往往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)，分號(hào)

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

17、出版社【附 錄】程序源代碼：#include#include#include#includestruct stacklifei1/數(shù)字棧的定義本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！double *base;double *top;s1;struct stacklifei2 / 運(yùn)算符棧的定義char *base;char *top;s2;double shuzhi40; /數(shù)字棧char fuha40;/符號(hào)棧int error;/ 出錯(cuò)標(biāo)識(shí)符FILE *file;char outfile30=lifeijisuanqi.txt;void jisuan() / 該函數(shù)對(duì)數(shù)字棧的前兩個(gè)棧頂/元素與

18、符號(hào)棧的棧頂元素完成一次運(yùn)算操作double a,b;b=*(s1.top-1);/ 取數(shù)字棧棧頂元素s1.top-;if(s1.top=s1.base)error=1;return ;/ 若?？?，出錯(cuò)a=*(s1.top-1);/取數(shù)字棧棧頂元素switch(*(s2.top-1)case +:a=a+b;break;case -:a=a-b;break;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！case *:a=a*b;break;case /:if(b=0)error=2;s2.top=s2.base;return ;/除數(shù)不為 0 else a=a/b;break;default :erro

19、r=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ù)完成對(duì)表達(dá)式的處理int i=0,k,h,flag,fuhao=0;double sum,j;s1.base=s1.top=shuzhi;s2.base=s2.top=fuha; /數(shù)字棧與符號(hào)棧初始化 *(s2.top)=#;/將 #入棧，方便循環(huán)s2.top+;while(s2.top!=s2.base)

20、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-19|i=0|cri+19)本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！/判斷小數(shù)點(diǎn)是否出錯(cuò)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 是個(gè)標(biāo)志記號(hào)，值不為 0 表明剛才轉(zhuǎn)換的值為負(fù)數(shù)*(

21、s1.top)=sum;s1.top+;elseswitch(cri)case -:if(cri-1=(|i=0)fuhao=1;i+;break;/判斷是不是負(fù)號(hào)，若不是則進(jìn)行與加號(hào)相同的操作/當(dāng)-出現(xiàn)在表達(dá)式第一位或是 (后第一位 ,則應(yīng)將其判為負(fù)號(hào) case +:/加、減號(hào)的優(yōu)先級(jí)只比 (和 =高，若棧頂元素為這兩者之一/就將其入棧，否則執(zhí)行運(yùn)算操作if(*(s2.top-1)=(|*(s2.top-1)=#)本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！*(s2.top)=cri;s2.top+;i+;else jisuan();break;case *:case /:/乘、除號(hào)的優(yōu)先級(jí)只比 *

22、 、/和低，若棧頂元素為這三者之一 /就執(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;/未入棧時(shí) (的優(yōu)先級(jí)最高，所以它一定要入棧/但一入棧其優(yōu)先級(jí)就應(yīng)降為最低case ):/注意：由于 ()運(yùn)算優(yōu)先級(jí)最高故我直接進(jìn)行運(yùn)算，/直到棧頂元素為 (后將 (出棧，故符號(hào)棧中一定沒(méi)有 )， /這也是我進(jìn)行以上優(yōu)先級(jí)判斷的前提if(*(s2.top-1)=()s2.top-;i+;else jisuan();break;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！case =:/表達(dá)式結(jié)束，若符號(hào)棧棧頂元素不為 #，進(jìn)行運(yùn)算/