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

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

2、量、變量、運(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)行插入或刪除操作的線(xiàn)性表。順序棧的存儲(chǔ) 結(jié)構(gòu)是利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置，base為棧底指針

3、，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉?biāo)記，每當(dāng)插入新的棧頂元素時(shí)，指針 top增1,刪除棧頂元素時(shí)，指針top 減1。2.2算法設(shè)計(jì)為了實(shí)現(xiàn)算符優(yōu)先算法。可以使用兩個(gè)工作棧。一個(gè)稱(chēng)為OPTR,用以寄存運(yùn)算符，另一個(gè)稱(chēng)做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á)式求值完畢(即 OPTR棧的棧頂元素和當(dāng)前讀入 的字符均為” #”)。2.3 ADT描述ADT Stack數(shù)據(jù)對(duì)象：D=引 產(chǎn) Ele

4、mSet,i=1,2,n, n三 0數(shù)據(jù)對(duì)象：R1=< 3i-ai4>|ai4,a Dg.，n約定an端為棧頂，ai端為棧底。基本操作：In itStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧SoGetTop(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)，

5、返回優(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(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

6、 *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)判斷字符是否是運(yùn)算符功能，運(yùn)算符即返回1,該功能只需簡(jiǎn)單的一 條語(yǔ)句即可實(shí)現(xiàn)，return(ch='+'|ch='-'|ch='*'|ch=7'|ch='('|ch=')'|ch=#。Precede(char c1,char

7、 c2)判斷運(yùn)算符優(yōu)先權(quán)功能，該函數(shù)判斷運(yùn)算符c1,c2的優(yōu)先權(quán)，具體優(yōu)先關(guān)系參照表1。(3) Operate© nt a,char op,i nt b操作數(shù)用對(duì)應(yīng)的運(yùn)算符進(jìn)行運(yùn)算功能。運(yùn)算結(jié)果直接 返回。num(int n)求操作數(shù)的長(zhǎng)度功能，需要用itoa函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函 數(shù)可求字符長(zhǎng)度。(5) EvalExpr()主要操作函數(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類(lèi)型棧，不能 滿(mǎn)足2位以上的整數(shù)，所以還需要定義一個(gè)int類(lèi)型的棧用來(lái)寄存操作數(shù)。/*

8、定義字符類(lèi)型棧*/struct stacklifei1 / 數(shù)字棧的定義double *base;double *top;s1;/struct stacklifei2/運(yùn)算符棧的定義char *base;char *top;s2;/該函數(shù)對(duì)數(shù)字棧的前兩個(gè)棧頂3.2計(jì)算功能的實(shí)現(xiàn)void jisua n()/元素與符號(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

9、;case '-':a=a-b;break;case '*':a=a*b;break;case '/':if(b=0)error=2;s2.top=s2.base;return ;/除數(shù)不為 0 else 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)void qiuzhi(char *

10、cr)該函數(shù)完成對(duì)表達(dá)式的處理int i=0,k,h,flag,fuhao=0;double sumj;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'&&criv='9'|cri='.')/若當(dāng)前的字符是數(shù)字，就將char型的數(shù)據(jù)轉(zhuǎn)換為double型if(cri='.')if(cri-1v'0'

11、|cri-1>'9'|i=0|cri+1v'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對(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 &#

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

13、;|*(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)=&#

14、39;(')s2.top-;i+；else jisua n() ;break;case '=':表達(dá)式結(jié)束，若符號(hào)棧棧頂元素不為'#'，進(jìn)行運(yùn)算否則退棧，結(jié)束if(*(s2.top-1)=#)s2.top-;else jisua n() ;break;default :i+; /清除空格及未定義符號(hào)3.5主菜單頁(yè)面的實(shí)現(xiàn)void mai n()char cr60;char c='a'file=fope n( outfile,"w+");/使用提示printf('*n");printf('*n&

15、quot;);*n")printf(”四則簡(jiǎn)易計(jì)算器nn");printf("輸入表達(dá)式例如 2+4= nn");printf("最后按#鍵 則會(huì)退出保存nn");printf("謝謝使用 nn");printf("*/循環(huán)輸入表達(dá)式，按#鍵退出 while(c!=#)error=0;printf("輸入表達(dá)式:n");gets(cr);fprintf(file,"表達(dá)式：%sn",cr);qiuzhi(cr);printf("任意鍵繼續(xù)，按#鍵退出:n&

16、quot;);c=getch();fclose(file);【附加一】 算符間的優(yōu)先關(guān)系如下:+-*/()=#+><<<<>>>->><<<>>>*>>>><>>>/>>>><>>>(<<<<<=>>)>>>>=>>>=<<<<<<=<#<<<<<&l

17、t;>=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)，引號(hào)，或者數(shù)據(jù)類(lèi)型 上。就一點(diǎn)小小的錯(cuò)誤也耽誤了我?guī)资昼?，所以說(shuō)細(xì)節(jié)很重要。程序設(shè)計(jì)時(shí)，也不要怕遇到錯(cuò)誤，在實(shí)際操作過(guò)程中犯的一些錯(cuò)誤還會(huì)有意外的收 獲，感覺(jué)課程設(shè)計(jì)很有意

18、思。在具體操作中這學(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é)出版社【附錄】程序源代碼：#i nclude<stdio.h>#i nclude<stdlib.h>#in clude<math.h>#in clu

19、de<c oni o.h>struct stacklifeil / 數(shù)字棧的定義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è)棧頂/元素與符號(hào)棧的棧頂元素完成一次運(yùn)算操作double a,b;b=*(

20、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;case '*':a=a*b;break;case 7':if(b=0)error=2;s2.top=s2.base;return ;/除數(shù)不為 0else a=a/b;break;default :error=1;fprin tf(fi

21、le,"%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 sumj;s1.base=s1.top=shuzhi;s2.base=s2.top=fuha;數(shù)字棧與符號(hào)棧初始化*(s2.top)=#;將'# '入棧，方便循環(huán)s2.top+;while(s2.top!=s2.base)s

22、um=0;flag=0;k=10;j=1;h=1;while(cri>='0'&&criv='9'|cri='.')/若當(dāng)前的字符是數(shù)字，就將char型的數(shù)據(jù)轉(zhuǎn)換為double型if(cri='.')if(cri-1<'0'|cri-1>'9'|i=0|cri+1<'0'|cri+1>'9')/判斷小數(shù)點(diǎn)是否出錯(cuò)error=1;break;elsek=1;h=10;elseflag=1;j=j*h;sum=sum*k+(c

23、ri-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ù)*(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í)只比 '

24、;('和 '='高，若棧頂元素為這兩者之一19就將其入棧，否則執(zhí)行運(yùn)算操作if(*(s2.top-1)='('|*(s2.top-1)=#) *(s2.top)=cri;s2.top+;i+；else jisua n( );break;case '/':乘、除號(hào)的優(yōu)先級(jí)只比'*'、7'和'"低，若棧頂元素為這三者之一就執(zhí)行運(yùn)算操作，否則將其入棧if(*(s2.top-1)='*'|*(s2.top-1)='/')jisua n();else*(s2.top)=cri

25、;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;case '=':/表達(dá)式結(jié)束，若符號(hào)棧棧頂元素不為 '#'，進(jìn)行運(yùn)算/否則退棧，結(jié)束if(*(s2.top-1)='#')s2.top-;else jisuan();break;default :i+; / 清除空格及未定義符號(hào)if(error)break;if(error|s1.top-1!=s1.ba