數(shù)據(jù)結(jié)構(gòu)模擬計算器課程設(shè)計

1、信號%才方的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告模擬計算器班級:學(xué)號：姓名：模擬計算器1、問題描述對于模擬計算器的設(shè)計，實際便是利用棧對一個表達式求值的問題。要求：對包含加，減，乘，除，括號的任意整型表達式進行求解2、設(shè)計思路表達式：任何表達式都是由操作數(shù)、運算符和界限符組成的有意義的式子。表達式求值時一般有后綴表示、中綴表示、前綴表示。操作數(shù)：可以是常數(shù)、變量、常量。運算符：從運算對象上分有單目運算符、雙目運算符、三目運算符。界限符：左右括號和表達式結(jié)束符。思路：我們平時用到的表達式即為我們所輸入的表達式(以#結(jié)束)，此表達式為中綴表達式，只要將此表達式利用棧來進出運算的符號轉(zhuǎn)換為后綴表達式，之后利用棧

2、來進出運算的數(shù)字將后綴表達式的值求出即可。3、數(shù)據(jù)結(jié)構(gòu)定義一般表達式的長度不會過長所以將順序棧的容量設(shè)為100已經(jīng)算是比較大了具體數(shù)據(jù)結(jié)構(gòu)如下：#definemaxsize100typedefdoubledatatypel;typedefchardatatype2;typedefstructstack1datatype1data1maxsize;inttop1;/*棧頂元素*/seqstack1,*pseqstack1;/*順序棧*/typedefstructstack2datatype2data2maxsize;inttop2;/*棧頂元素*/seqstack2,*pseqstack2;/*

3、順序棧*/4、系統(tǒng)功能模塊介紹(1) 判斷字符是否為操作數(shù)函數(shù)intisnum(char)當(dāng)輸入表達式時要利用棧對表達式中的數(shù)字和符號進行進棧出棧，因此要判斷表達式中的內(nèi)容是操作數(shù)、運算符還是界限符，給出相關(guān)信息。(2) 求運算符優(yōu)先級函數(shù)intpriority(char)對輸入的表達式中的內(nèi)容，若為運算符和界限符則要判斷其優(yōu)先級已完成其計算的先后順序。(3) 中綴表達式轉(zhuǎn)換為后綴表達式函數(shù)intinfix_exp_value(char*,char*)我們平時使用的為中綴表達式，但若利用棧則利用后綴表達式比較容易計算，因此要將中綴表達式轉(zhuǎn)換為后綴表達式，具體算法步驟如下：<1>co

4、unt=0,初始化運算符棧s,將結(jié)束符#加入運算符棧s中。<2>讀表達式字符=>w。<3>當(dāng)棧頂為#'并且w也是#'時結(jié)束；否則循環(huán)做下列步驟：<3.1>如果w是操作數(shù)判斷若count=0直接輸出，讀下一個字符=>w;轉(zhuǎn)<3>。若count!=0追加字符'',讀下一個字符=>w,轉(zhuǎn)<3>。<3.2>w若是運算符，則：count=1;<3.2.1>如果棧頂為(并且w為)則(出棧不輸出，讀下一個字符=>w,轉(zhuǎn)<3>。<3.2.1>如果棧

5、頂為(或者棧頂優(yōu)先級小于w優(yōu)先級，則w入棧，讀下一個字符=>w,轉(zhuǎn)<3>。否則：從運算符棧中出棧并輸出，轉(zhuǎn)<3>(4) 后綴表達式的求值函數(shù)doublepostfix_exp(char*)使用一個操作數(shù)棧，當(dāng)從左到右掃描表達式時，每遇到一個操作數(shù)就送入棧中保存，如果操作數(shù)不止一位，則保存在operand中，遇到下一個操作數(shù)時，執(zhí)行operand=operand*10+(ch-'0'),便可將操作數(shù)轉(zhuǎn)化為數(shù)字。每遇到一個運算符就從棧中取出兩個操作數(shù)進行當(dāng)前的計算，然后把結(jié)果在入棧，直到整個表達式結(jié)束，這時送入棧頂?shù)闹稻褪墙Y(jié)果。5、程序清單# incl

6、ude<stdio.h># include<malloc.h># include<conio.h># definemaxsize100typedefdoubledatatype1;typedefchardatatype2;typedefstructstack1datatype1data1maxsize;inttop1;/*棧頂元素*/seqstack1,*pseqstack1;/*順序棧*/typedefstructstack2datatype2data2maxsize;inttop2;/*棧頂元素*/seqstack2,*pseqstack2;/*順序棧*

7、/*棧的初始化*/pseqstacklinit_seqstack1(void)(pseqstack1S;S=(pseqstack1)malloc(sizeof(pseqstack1);if(S)S->top1=-1;returnS;pseqstack2init_seqstack2(void)(pseqstack2S;S=(pseqstack2)malloc(sizeof(pseqstack2);if(S)S->top2=-1;returnS;/*判斷?？?/intempty_seqstack1(pseqstack1S)(if(S->top1=-1)return1;elsere

8、turn0;intempty_seqstack2(pseqstack2S)(if(S->top2=-1)return1;elsereturn0;/*X入棧*/intpush_seqstack1(pseqstack1S,datatype1X)(if(S->top1=maxsize-1)(printf("棧滿，無法入棧！n");return0;)else(S->top1+;S->data1S->top1=X;return1;)intpush_seqstack2(pseqstack2S,datatype2X)(if(S->top2=maxsiz

9、e-1)(printf("棧滿，無法入棧！n");return0;)else(S->top2+;S->data2S->top2=X;return1;)/*X出棧*/intpop_seqstack1(pseqstack1S,datatype1*X)(if(empty_seqstack1(S)return0;else(*X=S->data1S->top1;S->top1-;return1;)intpop_seqstack2(pseqstack2S,datatype2*X)(if(empty_seqstack2(S)return0;else(*

10、X=S->data2S->top2;S->top2-;return1;/*求棧頂元素*/intgettop_seqstack1(pseqstack1S,datatype1*X)(if(empty_seqstack1(S)return0;else*X=S->data1S->top1;return1;)intgettop_seqstack2(pseqstack2S,datatype2*X)(if(empty_seqstack2(S)return0;else*X=S->data2S->top2;return1;)/*判斷字符是否為操作數(shù)。若是返回1,否則返回

11、0*/intisnum(charc)(if(c>='0'&&c<='9')return1;elsereturn0;)/*求后綴表達式的值*/doublepostfix_exp(char*A)(pseqstack1S;/*定義棧S*/doubleoperand=0;doubleresult;/*存放棧頂元素*/doublea;/*運算符ch前的操作數(shù)出棧存入a*/doubleb;/*運算符ch后的操作數(shù)出棧存入b*/doublec;/*c=achb*/charch;/*存放讀取到的表達式(A)的字符*/ch=*A+;/*讀表達式字符=&

12、gt;A*/S=init_seqstack1();/*初始化棧*/while(ch!='#')/*遇至U元素！='#'時*/(if(isnum(ch)/*判斷ch是否為數(shù)字字符，計算出操作數(shù)*/operand=operand*10+(ch-'0');else/*否則*/if(operand)push_seqstack1(S,operand);/*當(dāng)前字符不是數(shù)字，操作數(shù)結(jié)束，要入棧*/operand=0;if(ch!=''&&ch!='')pop_seqstack1(S,&b);pop_se

13、qstack1(S,&a);/*運算符ch后的操作數(shù)出棧存入b*/*運算符ch前的操作數(shù)出棧存入a*/switch(ch)/*求achb=?，將結(jié)果賦給c*/case'+':c=a+b;break;case'-':c=a-b;break;case'*':c=a*b;break;case'/':if(b!=0)c=a/b;elseprintf("分母為零!");push_seqstack1(S,c);/*將c壓入棧中*/ch=*A+;/*指針向下移動一位*/*遇到'#'循環(huán)結(jié)束*/gett

14、op_seqstack1(S,&result);/*此時棧頂元素即為計算結(jié)果result*/returnresult;/*優(yōu)先級判斷函數(shù)*/intpriority(charop)switch(op)case'#':return1;case')':return2;case'+':case'-':return3;case'*':case'/':return4;case'(':return5;default:return0;/*將指針infixexp指向的中綴表達式轉(zhuǎn)換為指針pos

15、tfixexp指向的后綴表達式*/intinfix_exp_value(char*infixexp,char*postfixexp)(pseqstack2S;/*定義棧S*/intcount=0;charw;/*存放讀取到的表達式(infixexp)的字符*/charc;/*存放棧頂元素*/chartopelement;/*存出棧元素*/S=init_seqstack2();/*初始化棧*/if(!S)/*棧的初始化判斷*/(printf("棧初始化失?。?quot;);return0;push_seqstack2(S,'#');/*將結(jié)束符'#'加入

16、運算符棧S中*/w=*infixexp;/*讀表達式字符=>w*/while(gettop_seqstack2(S,&c),c)!='#'|w!='#')/*<3>棧頂元素不等于#'或w不等于'#'時循環(huán)*/if(isnum(w)/*判斷w是否為操作數(shù)，若是直接輸出，讀下一個字符=>w,轉(zhuǎn)<3>*/(if(count)(*postfixexp=''postfixexp+;count=0;*postfixexp=w;postfixexp+;w=*(+infixexp);else/*

17、w若是運算符分類如下*/count=1;if(gettop_seqstack2(S,&c),c)='('&&w=')')/*如果棧頂為'('并且w為')'則'('出棧不輸出，讀下一個字符=>w,轉(zhuǎn)<3>*/pop_seqstack2(S,&topelement);/*將'('出棧存入topelement*/w=*(+infixexp);elseif(gettop_seqstack2(S,&c),c)='('|priority(

18、gettop_seqstack2(S,&c),c)<priority(w)/*如果棧頂為('或者棧頂優(yōu)先級小于w優(yōu)先級，則w入棧,讀下一個字符=>w,轉(zhuǎn)<3>*/push_seqstack2(S,w);w=*(+infixexp);else/*否貝U*/*從運算符棧中出棧并輸出，轉(zhuǎn)<3>*/pop_seqstack2(S,&topelement);*postfixexp=topelement;postfixexp+;*postfixexp='#'/*在指針postfixexp指向的后綴表達式結(jié)尾追加字符'#&#

19、39;*/*(+postfixexp)='0'/*在指針postfixexp指向的后綴表達式最后追加結(jié)束符0'*/return1;/*主函數(shù)*/intmain()inti=0;charAmaxsize;charBmaxsize;printf("請輸入表達式，如:11+22#,必須以#結(jié)尾！n");/*1+2*(9+7)-4/2#23+(12*3-2)/4+34*5/7)+108/9#*/Ai=getchar();while(Ai+!='#')Ai=getchar();Ai='0'infix_exp_value(A,B)

20、;printf("A=%sn",A);printf("B=%sn",B);printf("上式的結(jié)果為：");printf("%gn",postfix_exp(B);return0;getch();)6、運行與調(diào)試分析等(6.(1) 行與調(diào)試(1)、先輸入：3+5*2#后按回車求值，結(jié)果應(yīng)為：13-數(shù)據(jù)結(jié)構(gòu)上數(shù)據(jù)結(jié)構(gòu).侏浩與2。12年課程謖討、書上八模擬討算器.課本一|請輸入表達式，如：11十22#,必須以#號結(jié)尾!3+5*2#卜=3+5毋B二二352址+"上式的結(jié)果為：13Pressanykeytoco

21、ntinue(2)、先輸入：1+2*(9+7)-4/2#后按回車求值，結(jié)果應(yīng)為：31“比磷;I據(jù)結(jié)構(gòu)-數(shù)據(jù)結(jié)構(gòu)徐潔立口12年課程設(shè)計"書上模搜討算器一課本一請輸入表達式，如：11+22葩必須以首號結(jié)尾!1+2*(9+7)-4/2UA=l+2*(9+7)-4/2#B二二l20907+*-H9402/-#上式的結(jié)果為：31Pressanykeytocontinue_(3)、先輸入：15+3-2+(9/4)#后按回車求值，結(jié)果應(yīng)為：18.25國數(shù)據(jù)結(jié)構(gòu)I數(shù)據(jù)結(jié)構(gòu)除浩誼012年課程謾討，書上mtrn式模擬討算器_課本請輸入表達式，如：11+22#,必須以#號結(jié)尾!15+3-2+(9/4)#A

22、=15+3-2+(9/4)#B=153+02Y94/+#上式的結(jié)果為：18.25Pressanykeytocontinue(4)、先輸入：1+3-2+(4*5/10)-2#后按回車求值，結(jié)果應(yīng)為:35,數(shù)據(jù)結(jié)構(gòu)'數(shù)據(jù)結(jié)構(gòu).徐浩口1W年課程設(shè)過書上模擬計算器_謖本”電“請輸入表達式,如：11+22",必須以#號結(jié)尾!1+3-2+(4*5710)-2#A-=l+3-2+(4*B/10)-2#B-l3-n®2-405*010/+02-#上式的結(jié)果為：2Pressanykeytocontinue(5)、先輸入：23+(12*3-2)/4+34*5/7)+108/9#后按回車

23、求值，結(jié)果應(yīng)為：67.78571403"H：'數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)一徐浩場年課程設(shè)計書上起也、模擬計翼器一理本請輸入表達式,如：11+22禮必須以#號結(jié)尾!23+(12*3-2)/4+34*5/7)+108/9#A=23+(12*3-2)74+34*5/7)+108/9#E=2301203+(32H34/93405*07/-hH910809/+#上式的結(jié)果為：67,7857Pressanykeytocontinue(6.(2) 析根據(jù)以上結(jié)果可以知道本程序正確，本程序中intisnum(charc)doublepostfix_exp(char*A)intpriority(char

24、op)intinfix_exp_value(char*infixexp,char*postfixexp)等函數(shù)原型為課本P64-P68的函數(shù)，單元函數(shù)只能對0-9之間的數(shù)進行基本的算術(shù)運算，無法對大于9的數(shù)進行運算，因而對函數(shù)doublepostfix_exp(char*A)與int(6.2.1)函數(shù)doublepostfix_exp(char*A)修改前后對比修改前infix_exp_value(char*infixexp,char*postfixexp)進行一定的修改，便可以運算整形數(shù)字，doublepostfi«_ewp(char*A)<一p5eqstacKS;charr

25、esultcharch;ch=*A+;S-init_seqstack();(if(isnuii(ch)pushseqst.ack(S,(char)(cti,fl*);else<pop_5eqstack(SB&b);pop_seqstack(S;5uitch(ch)doublypostfix_exp(ctiar*fi)pseqstacklS;/看定義棧$江/Uourieoperand=0;Idoubleresult;/*存放低頂元素量/doublea;/喳黑銖h前的速作藪出筏存入a*/doubleb;/嚙簟將M后的榛作數(shù)出程特入皿/doublec;/*c-actib*/charch

26、;八在放讀取到的表達式(射的字符wch=*ft+;/聯(lián)表達式字符=>口*/S-init_seqstack1()£仁初始化棧巡到元素，=#時黑/“(isrHm(cli)/,判斷cii是否為數(shù)字帖符，計寫operand=operand*1B+(ch-'flbelse/否則”IF(operand)<一push_5eqstack1(Svoperand)operand-fl;if(ch*='0,&&chf=,1)pop_seqstack1CS;/*jzpop_seq弓tacH1(S,&a);/噬switch(cti)外求achU=?1將至修改后(6.2.2)函數(shù)in