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

-.z..//v.軟件技術(shù)根底實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：表達(dá)式計(jì)算器系別：通信工程年級：班級：學(xué)生**：學(xué)生**："數(shù)據(jù)構(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)：括號(hào)的處理、乘除的優(yōu)先級高于加減

1．前言在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號(hào)組成。由于不同的運(yùn)算符具有不同的優(yōu)先級，又要考慮括號(hào)，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)展。因而在程序設(shè)計(jì)時(shí)，借助棧實(shí)現(xiàn)。算法輸入：一個(gè)算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號(hào)組成〔以字符串形式輸入〕。為簡化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為+、-*、/、=，用#表示完畢。算法輸出：表達(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ù)構(gòu)造設(shè)計(jì)任何一個(gè)表達(dá)式都是由操作符，運(yùn)算符和界限符組成的。我們分別用順序棧來存放表達(dá)式的操作數(shù)和運(yùn)算符。棧是限定于緊僅在表尾進(jìn)展插入或刪除操作的線性表。順序棧的存儲(chǔ)構(gòu)造是利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?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á)式，假設(shè)是操作符即進(jìn)OPND棧，假設(shè)是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比擬優(yōu)先權(quán)后作相應(yīng)的操作，直至整個(gè)表達(dá)式求值完畢〔即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為〞#〞〕。2.3ADT描述ADTStack{數(shù)據(jù)對象：D={|∈ElemSet,i=1,2,…，n,n≧0}數(shù)據(jù)對象：R1={<>|,,i=2,…，n}約定端為棧頂，端為棧底。根本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧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)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運(yùn)算符。操作結(jié)果：a與b進(jìn)展運(yùn)算，op為運(yùn)算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長度。EvalE*pr()初始條件：輸入表達(dá)式合法。操作結(jié)果：返回表達(dá)式的最終結(jié)果。}ADTStack2.4功能模塊分析1.棧的根本功能。InitStack(Stack*s)和InitStack2(Stack2*s)分別構(gòu)造運(yùn)算符棧與構(gòu)造操作數(shù)棧，Push(Stack*s,charch)運(yùn)算符棧插入ch為新的棧頂元素，Push2(Stack2*s,intch)操作數(shù)棧插入ch為新的棧頂元素，Pop(Stack*s)刪除運(yùn)算符棧s的棧頂元素，用p返回其值，Pop2(Stack2*s)刪除操作數(shù)棧s的棧頂元素，用p返回其值，GetTop(Stacks)用p返回運(yùn)算符棧s的棧頂元素，GetTop2(Stack2s)用p返回操作數(shù)棧s的棧頂元素。2.其它功能分析。(1)In(charch)判斷字符是否是運(yùn)算符功能，運(yùn)算符即返回1，該功能只需簡單的一條語句即可實(shí)現(xiàn)，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。(2)Precede(charc1,charc2)判斷運(yùn)算符優(yōu)先權(quán)功能，該函數(shù)判斷運(yùn)算符c1,c2的優(yōu)先權(quán)，具體優(yōu)先關(guān)系參照表1。(3)Operate(inta,charop,intb)操作數(shù)用對應(yīng)的運(yùn)算符進(jìn)展運(yùn)算功能。運(yùn)算結(jié)果直接返回。(4)num(intn)求操作數(shù)的長度功能，需要用itoa函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函數(shù)可求字符長度。(5)EvalE*pr()主要操作函數(shù)運(yùn)算功能。分析詳細(xì)見"3.詳細(xì)設(shè)計(jì)…3.2〞。3．詳細(xì)設(shè)計(jì)3.1數(shù)據(jù)存儲(chǔ)構(gòu)造設(shè)計(jì)因?yàn)楸磉_(dá)式是由操作符，運(yùn)算符和界限符組成的。如果只用一個(gè)char類型棧，不能滿足2位以上的整數(shù)，所以還需要定義一個(gè)int類型的棧用來存放操作數(shù)。/*定義字符類型棧*/structstacklifei1//數(shù)字棧的定義{ double*base; double*top;}s1;/structstacklifei2//運(yùn)算符棧的定義{ char*base; char*top;}s2;3.2計(jì)算功能的實(shí)現(xiàn)voidjisuan()//該函數(shù)對數(shù)字棧的前兩個(gè)棧頂//元素與符號(hào)棧的棧頂元素完成一次運(yùn)算操作{ doublea,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ù)不為0 elsea=a/b;break; default:error=1; } fprintf(file,"%lf%c%lf=%lf\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)voidqiuzhi(char*cr)該函數(shù)完成對表達(dá)式的處理{ inti=0,k,h,flag,fuhao=0; doublesum,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(cr[i]>='0'&&cr[i]<='9'||cr[i]=='.') //假設(shè)當(dāng)前的字符是數(shù)字，就將char型的數(shù)據(jù)轉(zhuǎn)換為double型 { if(cr[i]=='.') { if(cr[i-1]<'0'||cr[i-1]>'9'||i==0||cr[i+1]<'0'||cr[i+1]>'9') {error=1;break;} else {k=1;h=10;} } else { flag=1;j=j*h; sum=sum*k+(cr[i]-48)/j; } i++; }3.4對函數(shù)表達(dá)式每個(gè)字符的操作switch(cr[i]) { case'-':if(cr[i-1]=='('||i==0){fuhao=1;i++;break;} //判斷是不是負(fù)號(hào)，假設(shè)不是則進(jìn)展與加號(hào)一樣的操作 //當(dāng)'-'出現(xiàn)在表達(dá)式第一位或是'('后第一位,則應(yīng)將其判為負(fù)號(hào) case'+': //加、減號(hào)的優(yōu)先級只比'('和'='高，假設(shè)棧頂元素為這兩者之一 //就將其入棧，否則執(zhí)行運(yùn)算操作 if(*(s2.top-1)=='('||*(s2.top-1)=='#') { *(s2.top)=cr[i]; s2.top++; i++; } elsejisuan();break; case'*': case'/': //乘、除號(hào)的優(yōu)先級只比'*'、'/'和'^'低，假設(shè)棧頂元素為這三者之一 //就執(zhí)行運(yùn)算操作，否則將其入棧 if(*(s2.top-1)=='*'||*(s2.top-1)=='/')jisuan(); else { *(s2.top)=cr[i]; s2.top++; i++; }break; case'(':*(s2.top)=cr[i];s2.top++;i++;break; //未入棧時(shí)'('的優(yōu)先級最高，所以它一定要入棧 //但一入棧其優(yōu)先級就應(yīng)降為最低 case')': //注意：由于'()'運(yùn)算優(yōu)先級最高故我直接進(jìn)展運(yùn)算， //直到棧頂元素為'('后將'('出棧，故符號(hào)棧中一定沒有')'， //這也是我進(jìn)展以上優(yōu)先級判斷的前提 if(*(s2.top-1)=='(') { s2.top--; i++; } elsejisuan();break; case'=': //表達(dá)式完畢，假設(shè)符號(hào)棧棧頂元素不為'#'，進(jìn)展運(yùn)算 //否則退棧，完畢 if(*(s2.top-1)=='#') { s2.top--; } elsejisuan();break; default:i++;//去除空格及未定義符號(hào) }3.5主菜單頁面的實(shí)現(xiàn)voidmain(){ charcr[60]; charc='a'; file=fopen(outfile,"w+"); //使用提示 printf("*******************************************************************************\n"); printf("*********************************李斐計(jì)算器************************************\n"); printf("四則簡易計(jì)算器\n\n"); printf("輸入表達(dá)式例如2+4=\n\n"); printf("最后按#鍵則會(huì)退出保存\n\n"); printf("謝謝使用\n\n"); printf("\n"); printf("******************************************************************************\n"); //循環(huán)輸入表達(dá)式，按'#'鍵退出 while(c!='#') { error=0; printf("輸入表達(dá)式:\n"); gets(cr); fprintf(file,"表達(dá)式：%s\n",cr); qiuzhi(cr); printf("任意鍵繼續(xù)，按#鍵退出:\n"); c=getch(); } fclose(file);}【附加一】算符間的優(yōu)先關(guān)系如下：+-*/()=#+><<<<>>>->><<<>>>*>>>><>>>/>>>><>>>(<<<<<=>>)>>>>=>>>=<<<<<<=<#<<<<<<>=4．軟件測試1.運(yùn)行成功后界面。2.輸入正確的表達(dá)式后。3.更改表達(dá)式，帶括號(hào)輸出5．心得體會(huì)這次課程設(shè)計(jì)讓我再一次加了解大一學(xué)到的C和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)構(gòu)造。課設(shè)題目要求不僅要求對課本知識(shí)有較深刻的了解，同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的思維和動(dòng)手能力和更加了解編程思想和編程技巧。這次課程設(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ù)類型上。就一點(diǎn)小小的錯(cuò)誤也耽誤了我?guī)资昼?，所以說細(xì)節(jié)很重要。程序設(shè)計(jì)時(shí)，也不要怕遇到錯(cuò)誤，在實(shí)際操作過程中犯的一些錯(cuò)誤還會(huì)有意外的收獲，感覺課程設(shè)計(jì)很有意思。在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)構(gòu)造的理論知識(shí)得到穩(wěn)固，到達(dá)課程設(shè)計(jì)的根本目的，也發(fā)現(xiàn)自己的缺乏之出，在以后的上機(jī)中應(yīng)更加注意，同時(shí)體會(huì)到C語言具有的語句簡潔，使用靈活，執(zhí)行效率高等特點(diǎn)。發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù)表達(dá)式有了深刻的理解。最后，感謝教師在這門數(shù)據(jù)構(gòu)造課程的悉心指導(dǎo)，祝教師和助教身體安康，萬事如意！【參考文獻(xiàn)】1."數(shù)據(jù)構(gòu)造(C語言版)"嚴(yán)蔚敏清華大學(xué)2."C程序設(shè)計(jì)"譚浩強(qiáng)清華大學(xué)【附錄】程序源代碼：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<conio.h>structstacklifei1//數(shù)字棧的定義{ double*base; double*top;}s1;structstacklifei2//運(yùn)算符棧的定義{ char*base; char*top;}s2;doubleshuzhi[40];//數(shù)字棧charfuha[40];//符號(hào)棧interror;//出錯(cuò)標(biāo)識(shí)符FILE*file;charoutfile[30]="\lifeijisuanqi.t*t";voidjisuan()//該函數(shù)對數(shù)字棧的前兩個(gè)棧頂//元素與符號(hào)棧的棧頂元素完成一次運(yùn)算操作{ doublea,b; b=*(s1.top-1);//取數(shù)字棧棧頂元素 s1.top--; if(s1.top==s1.base) { error=1; return; }//假設(shè)?？?，出錯(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'/':if(b==0){error=2;s2.top=s2.base;return;}//除數(shù)不為0 elsea=a/b;break; default:error=1; } fprintf(file,"%lf%c%lf=%lf\n",*(s1.top-1),*(s2.top-1),b,a); *(s1.top-1)=a;//將運(yùn)算結(jié)果入棧 s2.top--;//運(yùn)算符退棧 return;}voidqiuzhi(char*cr)// qiuzhi()；該函數(shù)完成對表達(dá)式的處理{ inti=0,k,h,flag,fuhao=0; doublesum,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) { sum=0; flag=0; k=10;j=1;h=1; while(cr[i]>='0'&&cr[i]<='9'||cr[i]=='.') //假設(shè)當(dāng)前的字符是數(shù)字，就將char型的數(shù)據(jù)轉(zhuǎn)換為double型 { if(cr[i]=='.') { if(cr[i-1]<'0'||cr[i-1]>'9'||i==0||cr[i+1]<'0'||cr[i+1]>'9') //判斷小數(shù)點(diǎn)是否出錯(cuò) {error=1;break;} else {k=1;h=10;} } else { flag=1;j=j*h; sum=sum*k+(cr[i]-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++; } else { switch(cr[i]) { case'-':if(cr[i-1]=='('||i==0){fuhao=1;i++;break;} //判斷是不是負(fù)號(hào)，假設(shè)不是則進(jìn)展與加號(hào)一樣的操作 //當(dāng)'-'出現(xiàn)在表達(dá)式第一位或是'('后第一位,則應(yīng)將其判為負(fù)號(hào) case'+': //加、減號(hào)的優(yōu)先級只比'('和'='高，假設(shè)棧頂元素為這兩者之一 //就將其入棧，否則執(zhí)行運(yùn)算操作 if(*(s2.top-1)=='('||*(s2.top-1)=='#') { *(s2.top)=cr[i]; s2.top++; i++; } elsejisuan();break; case'*': case'/': //乘、除號(hào)的優(yōu)先級只比'*'、'/'和'^'低，假設(shè)棧頂元素為這三者之一 //就執(zhí)行運(yùn)算操作，否則將其入棧 if(*(s2.top-1)=='*'||*(s2.top-1)=='/')jisuan(); else { *(s2.top)=cr[i]; s2.top++; i++; }break; case'(':*(s2.top)=cr[i];s2.top++;i++;break; //未入棧時(shí)'('的優(yōu)先級最高，所以它一定要入棧 //但一入棧其優(yōu)先級就應(yīng)降為最低 case')': //注意：由于'()'運(yùn)算優(yōu)先級最高故我直接進(jìn)展運(yùn)算， //直到棧頂元素為'('后將'('出棧，故符號(hào)棧中一定沒有')'， //這也是我進(jìn)展以上優(yōu)先級判斷的前提 if(*(s2.top-1)=='(') { s2.top--; i++; } elsejisuan();break; case'=': //表達(dá)式完畢，假設(shè)符號(hào)棧棧頂元素不為'#'，進(jìn)展運(yùn)算 //否則退棧，完畢 if(*(s2.top-1)=='#') { s2.top--; } elsejisuan();break; default:i++;//去除空格及未定義符號(hào) } } if(error)break; } if(error||s1.top-1!=s1.base) //假設(shè)運(yùn)行