數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)--模擬簡(jiǎn)單計(jì)算器

1、<p>　　通達(dá)學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告</p><p>　?。?2014/2015學(xué)年 第 二 學(xué)期 ）</p><p>　　題 目： 模擬簡(jiǎn)單計(jì)算器 </p><p><b>　　一、課題內(nèi)容和要求</b></p><p>　　利用所學(xué)的數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，設(shè)計(jì)一個(gè)計(jì)算器（90）<

2、;/p><p>　　輸入：帶有括號(hào)、+，-，X,/ 的表達(dá)式；</p><p><b>　　輸出：運(yùn)算結(jié)果</b></p><p>　　實(shí)例：輸入：（4*3-（2+1））*2</p><p><b>　　輸出： 18</b></p><p><b>　　要求：</

3、b></p><p>　　1）對(duì)不合法輸入進(jìn)行檢測(cè)并提示；</p><p>　　2）對(duì)合法輸入求出正確解；</p><p><b>　　二、需求分析</b></p><p>　　本程序主要是采用棧的理論知識(shí)，主要用到兩個(gè)結(jié)構(gòu)體棧，一個(gè)用來(lái)轉(zhuǎn)化表達(dá)式，一個(gè)用來(lái)計(jì)算表達(dá)式。</p><p>&l

4、t;b>　　三、概要設(shè)計(jì)</b></p><p><b>　　1設(shè)計(jì)理念 </b></p><p>　　首先，用一個(gè)字符數(shù)組來(lái)存儲(chǔ)用戶輸入的中綴表達(dá)式。然后用棧來(lái)把這個(gè)表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，轉(zhuǎn)化時(shí)要進(jìn)行符號(hào)優(yōu)先級(jí)比較，這里將‘*’‘/’的優(yōu)先級(jí)定為2，‘+’‘-’定為1，括號(hào)和‘=’定為0。具體思想如下：例如用戶輸入了1+2*3=，將其存放入一個(gè)字

5、符數(shù)組中。先在棧的底部存放一個(gè)‘=’號(hào)符，用作符號(hào)優(yōu)先級(jí)比較。首先將1存放到另外一個(gè)字符數(shù)組s1中，再將‘+’號(hào)入棧。入棧的同時(shí)與底部的‘=’比較優(yōu)先級(jí)，‘+’的優(yōu)先級(jí)高于‘=’，所以不出棧，之后將2存放入s2中，然后再將‘*’入棧，入棧的同時(shí)與‘+’比較符號(hào)優(yōu)先級(jí)，‘*’比‘+’高，所以不出棧。再將3存入s2中。之后將棧中不是‘=’的運(yùn)算符都彈出棧，并依次存入s2中。所以s2中的表達(dá)式為123*+。之后進(jìn)行計(jì)算，計(jì)算時(shí)用到浮點(diǎn)棧。首先

6、將s2中的字符依次入棧，遇到運(yùn)算符時(shí)進(jìn)行計(jì)算。所以將123入棧后，再將‘*’入棧的同時(shí)，將前面兩個(gè)數(shù)字進(jìn)行運(yùn)算，算出結(jié)果為6并存入棧中，之后再將‘+’入棧，再與1進(jìn)行運(yùn)算，結(jié)果即為7，然后輸出結(jié)果。</p><p><b>　　2.子函數(shù)功能</b></p><p>　　pseqstack1 init_seqstack1(void)</p><p&

7、gt;<b>　　{</b></p><p>　　pseqstack1 S;</p><p>　　S=(pseqstack1)malloc(sizeof(pseqstack1));</p><p><b>　　if(S)</b></p><p>　　S->top1=-1;</p>

8、<p><b>　　return S;</b></p><p><b>　　}初始化棧</b></p><p>　　int empty_seqstack1(pseqstack1 S)</p><p><b>　　{</b></p><p>　　if(S->to

9、p1==-1)</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>&

10、lt;b>　　判斷棧是否為空</b></p><p>　　int push_seqstack1(pseqstack1 S,datatype1 X</p><p><b>　　進(jìn)棧</b></p><p>　　int pop_seqstack1(pseqstack1 S,datatype1 *X)</p><

11、p><b>　　出棧</b></p><p>　　int GetTop(seqstack *s) </p><p><b>　　取棧頂元素</b></p><p>　　int PP(char op,char c) </p><p>　　比較棧頂元素與當(dāng)前讀入的運(yùn)算符的優(yōu)先級(jí)</p&

12、gt;<p>　　int Ope(int a,char m,int b) </p><p>　　從數(shù)字棧中取出的兩個(gè)數(shù)的計(jì)算</p><p>　　int priority(char op)</p><p><b>　　優(yōu)先級(jí)判斷函數(shù)</b></p><p>　　int infix_exp_value(cha

13、r *infixexp,char *postfixexp</p><p>　　將指針infixexp指向的中綴表達(dá)式轉(zhuǎn)換為指針postfixexp指向的后綴表達(dá)式</p><p>　　double postfix_exp(char *A)</p><p><b>　　求后綴表達(dá)式的值</b></p><p><b&

14、gt;　　3.函數(shù)的調(diào)用</b></p><p><b>　　四、詳細(xì)設(shè)計(jì)</b></p><p>　　# include <stdio.h></p><p>　　# include <malloc.h></p><p>　　# include <conio.h></

15、p><p>　　# define maxsize 100</p><p>　　typedef double datatype1;</p><p>　　typedef char datatype2;</p><p>　　typedef struct stack1 </p><p><b>　　{</b&

16、gt;</p><p>　　datatype1 data1[maxsize];</p><p>　　int top1;/*棧頂元素*/</p><p>　　}seqstack1,*pseqstack1; /*順序棧*/</p><p>　　typedef struct stack2 </p><p><b

17、>　　{</b></p><p>　　datatype2 data2[maxsize];</p><p>　　int top2;/*棧頂元素*/</p><p>　　}seqstack2,*pseqstack2; /*順序棧*/</p><p><b>　　/*棧的初始化*/</b></p

18、><p>　　pseqstack1 init_seqstack1(void)</p><p><b>　　{</b></p><p>　　pseqstack1 S;</p><p>　　S=(pseqstack1)malloc(sizeof(pseqstack1));</p><p><b>

19、;　　if(S)</b></p><p>　　S->top1=-1;</p><p><b>　　return S;</b></p><p><b>　　}</b></p><p>　　pseqstack2 init_seqstack2(void)</p><p

20、><b>　　{</b></p><p>　　pseqstack2 S;</p><p>　　S=(pseqstack2)malloc(sizeof(pseqstack2));</p><p><b>　　if(S)</b></p><p>　　S->top2=-1;</p>

21、<p><b>　　return S;</b></p><p><b>　　}</b></p><p><b>　　/*判斷?？?/</b></p><p>　　int empty_seqstack1(pseqstack1 S)</p><p><b>

22、　　{</b></p><p>　　if(S->top1==-1)</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p&

23、gt;<b>　　}</b></p><p>　　int empty_seqstack2(pseqstack2 S)</p><p><b>　　{</b></p><p>　　if(S->top2==-1)</p><p><b>　　return 1;</b><

24、/p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　/*X入棧*/</b></p><p>　　int push_seq

25、stack1(pseqstack1 S,datatype1 X)</p><p><b>　　{</b></p><p>　　if(S->top1==maxsize-1)</p><p><b>　　{</b></p><p>　　printf("棧滿，無(wú)法入棧！\n");

26、</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　S->top1++;&

27、lt;/p><p>　　S->data1[S->top1]=X;</p><p>　　return 1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int push_seqstack2(pseqstack2

28、S,datatype2 X)</p><p><b>　　{</b></p><p>　　if(S->top2==maxsize-1)</p><p><b>　　{</b></p><p>　　printf("棧滿，無(wú)法入棧！\n");</p><p&

29、gt;<b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　S->top2++;</p><p&g

30、t;　　S->data2[S->top2]=X;</p><p>　　return 1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　/*X出棧*/</b></p><p>　

31、　int pop_seqstack1(pseqstack1 S,datatype1 *X)</p><p><b>　　{</b></p><p>　　if(empty_seqstack1(S))</p><p><b>　　return 0;</b></p><p><b>　　else

32、</b></p><p><b>　　{</b></p><p>　　*X=S->data1[S->top1];</p><p>　　S->top1--;</p><p>　　return 1;</p><p><b>　　}</b></

33、p><p><b>　　}</b></p><p>　　int pop_seqstack2(pseqstack2 S,datatype2 *X)</p><p><b>　　{</b></p><p>　　if(empty_seqstack2(S))</p><p><b&

34、gt;　　return 0;</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　*X=S->data2[S->top2];</p><p>　　S->top2--;</p><p>

35、　　return 1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　/*求棧頂元素*/</b></p><p>　　int gettop_seqstack1(pseqstack1 S,datatype1 *X)&

36、lt;/p><p><b>　　{</b></p><p>　　if(empty_seqstack1(S))</p><p>　　return 0; </p><p><b>　　else</b></p><p>　　*X=S->data1[S->

37、top1];</p><p>　　return 1;</p><p><b>　　}</b></p><p>　　int gettop_seqstack2(pseqstack2 S,datatype2 *X)</p><p><b>　　{</b></p><p>　　i

38、f(empty_seqstack2(S))</p><p>　　return 0; </p><p><b>　　else</b></p><p>　　*X=S->data2[S->top2];</p><p>　　return 1;</p><p><b

39、>　　}</b></p><p>　　/*判斷字符是否為操作數(shù)。若是返回1，否則返回0*/</p><p>　　int isnum(char c)</p><p><b>　　{</b></p><p>　　if(c>='0' && c<='9'

40、;)</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　/*求后

41、綴表達(dá)式的值*/</p><p>　　double postfix_exp(char *A)</p><p><b>　　{</b></p><p>　　pseqstack1 S;/*定義棧S*/</p><p>　　double operand=0;</p><p>　　double resu

42、lt;/*存放棧頂元素*/</p><p>　　double a;/*運(yùn)算符ch前的操作數(shù)出棧存入a*/</p><p>　　double b;/*運(yùn)算符ch后的操作數(shù)出棧存入b*/</p><p>　　double c;/*c==a ch b*/</p><p>　　char ch;/*存放讀取到的表達(dá)式(A)的字符*/<

43、/p><p>　　ch=*A++;/*讀表達(dá)式字符=>A*/</p><p>　　S=init_seqstack1();/*初始化棧*/</p><p>　　while(ch!='#')/*遇到元素!='#'時(shí)*/</p><p><b>　　{</b></p><

44、;p>　　if(isnum(ch))/*判斷ch是否為數(shù)字字符,計(jì)算出操作數(shù)*/</p><p>　　operand=operand*10+(ch-'0');</p><p>　　else/*否則*/</p><p><b>　　{</b></p><p>　　if(operand)</p&

45、gt;<p><b>　　{</b></p><p>　　push_seqstack1(S,operand);/*當(dāng)前字符不是數(shù)字,操作數(shù)結(jié)束,要入棧*/</p><p>　　operand=0;</p><p><b>　　}</b></p><p>　　if(ch!='@&

46、#39; && ch!=' ')</p><p><b>　　{</b></p><p>　　pop_seqstack1(S,&b);/*運(yùn)算符ch后的操作數(shù)出棧存入b*/</p><p>　　pop_seqstack1(S,&a);/*運(yùn)算符ch前的操作數(shù)出棧存入a*/</p>

47、;<p>　　switch(ch)/*求 a ch b==? ,將結(jié)果賦給 c */</p><p><b>　　{</b></p><p>　　case '+' : </p><p><b>　　c=a+b;</b></p><p><b>　　break

48、;</b></p><p>　　case '-' : </p><p><b>　　c=a-b;</b></p><p><b>　　break;</b></p><p>　　case '*' : </p><p><b>

49、;　　c=a*b;</b></p><p><b>　　break;</b></p><p>　　case '/' :</p><p><b>　　if(b!=0)</b></p><p><b>　　c=a/b;</b></p>&l

50、t;p><b>　　else</b></p><p>　　printf("分母為零!");</p><p><b>　　}</b></p><p>　　push_seqstack1(S,c);/*將c壓入棧中*/</p><p><b>　　}</b>

51、;</p><p><b>　　}</b></p><p>　　ch=*A++;/*指針向下移動(dòng)一位*/</p><p>　　}/*遇到'#'循環(huán)結(jié)束*/</p><p>　　gettop_seqstack1(S,&result);/*此時(shí)棧頂元素即為計(jì)算結(jié)果result*/</p>

52、<p>　　return result;</p><p><b>　　}</b></p><p>　　/*優(yōu)先級(jí)判斷函數(shù)*/</p><p>　　int priority(char op)</p><p><b>　　{</b></p><p>　　switch

53、(op)</p><p><b>　　{</b></p><p>　　case '#': return 1;</p><p>　　case ')': return 2;</p><p>　　case '+': </p><p>　　case '

54、;-': return 3;</p><p>　　case '*': </p><p>　　case '/': return 4;</p><p>　　case '(': return 5;</p><p>　　default : return 0;</p><p&

55、gt;<b>　　} </b></p><p><b>　　}</b></p><p>　　/*將指針infixexp指向的中綴表達(dá)式轉(zhuǎn)換為指針postfixexp指向的后綴表達(dá)式*/</p><p>　　int infix_exp_value(char *infixexp,char *postfixexp)</

56、p><p><b>　　{</b></p><p>　　pseqstack2 S;/*定義棧S*/</p><p>　　int count=0;</p><p>　　char w;/*存放讀取到的表達(dá)式(infixexp)的字符*/</p><p>　　char c;/*存放棧頂元素*/<

57、/p><p>　　char topelement;/*存出棧元素*/</p><p>　　S=init_seqstack2();/*初始化棧*/</p><p>　　if(!S)/*棧的初始化判斷*/</p><p><b>　　{</b></p><p>　　printf("棧初始化失

58、敗!");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　push_seqstack2(S,'#');/*將結(jié)束符'# '加入運(yùn)算符棧S中*/</p><p>　　w=*i

59、nfixexp;/*讀表達(dá)式字符=>w*/</p><p>　　while((gettop_seqstack2(S,&c),c)!='#'||w!='#')/*<3>棧頂元素不等于'#'或w不等于'#'時(shí)循環(huán)*/</p><p><b>　　{</b></p>&

60、lt;p>　　if(isnum(w))/*判斷w是否為操作數(shù),若是直接輸出,讀下一個(gè)字符=>w,轉(zhuǎn)<3>*/</p><p><b>　　{</b></p><p><b>　　if(count)</b></p><p><b>　　{</b></p><p

61、>　　*postfixexp='@';</p><p>　　postfixexp++;</p><p><b>　　count=0;</b></p><p><b>　　}</b></p><p>　　*postfixexp=w;</p><p>　　p

62、ostfixexp++;</p><p>　　w=*(++infixexp);</p><p><b>　　}</b></p><p>　　else/*w若是運(yùn)算符分類如下*/</p><p><b>　　{</b></p><p><b>　　count=1;&

63、lt;/b></p><p>　　if( (gettop_seqstack2(S,&c),c)=='(' && w==')' )</p><p>　　{/*如果棧頂為'('并且w為')'則'('出棧不輸出,讀下一個(gè)字符=>w,轉(zhuǎn)<3>*/</p>&

64、lt;p>　　pop_seqstack2(S,&topelement); /*將'('出棧存入topelement*/</p><p>　　w=*(++infixexp);</p><p><b>　　}</b></p><p><b>　　else</b></p><p

65、>　　if( (gettop_seqstack2(S,&c),c)=='(' || priority( (gettop_seqstack2(S,&c),c) ) < priority(w) )</p><p>　　{/*如果棧頂為'('或者棧頂優(yōu)先級(jí)小于w優(yōu)先級(jí),則w入棧,讀下一個(gè)字符=>w，轉(zhuǎn)<3>*/</p><

66、p>　　push_seqstack2(S,w);</p><p>　　w=*(++infixexp);</p><p><b>　　}</b></p><p>　　else/*否則*/</p><p>　　{/*從運(yùn)算符棧中出棧并輸出,轉(zhuǎn)<3>*/</p><p>　　pop_s

67、eqstack2(S,&topelement);</p><p>　　*postfixexp=topelement;</p><p>　　postfixexp++;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

68、t;<b>　　}</b></p><p>　　*postfixexp='#';/*在指針postfixexp指向的后綴表達(dá)式結(jié)尾追加字符'#'*/</p><p>　　*(++postfixexp)='\0';/*在指針postfixexp指向的后綴表達(dá)式最后追加結(jié)束符'\0'*/</p>

69、<p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　/*主函數(shù)*/</b></p><p>　　int main()</p><p><b>　　{ </b></p>

70、<p><b>　　int i=0;</b></p><p>　　char A[maxsize];</p><p>　　char B[maxsize];</p><p>　　printf("請(qǐng)輸入表達(dá)式,如:11+22#,必須以#號(hào)結(jié)尾!\n"); </p><p>　　/* 1+2*(

71、9+7)-4/2# 23+((12*3-2)/4+34*5/7)+108/9# */</p><p>　　A[i]=getchar();</p><p>　　while(A[i++]!='#')</p><p><b>　　{</b></p><p>　　A[i]=getchar();</p>

72、;<p><b>　　}</b></p><p>　　A[i]='\0';</p><p>　　infix_exp_value(A,B);</p><p>　　printf("A==%s\n",A);</p><p>　　printf("B==%s\n"

73、;,B);</p><p>　　printf("上式的結(jié)果為: ");</p><p>　　printf("%g\n",postfix_exp(B));</p><p><b>　　return 0;</b></p><p><b>　　getch();</b>

74、;</p><p><b>　　}</b></p><p><b>　　五、測(cè)試及結(jié)果分析</b></p><p><b>　　加法測(cè)試</b></p><p><b>　　1+2+3=6</b></p><p><b>

75、　　減法測(cè)試</b></p><p><b>　　5-2-1=2</b></p><p><b>　　乘法測(cè)試</b></p><p><b>　　1*2*3=6</b></p><p><b>　　除法測(cè)試</b></p>&l

76、t;p><b>　　9/3/2=1.5</b></p><p><b>　　混合運(yùn)算</b></p><p><b>　　1*（3+2）</b></p><p>　　六、調(diào)試過(guò)程中的問(wèn)題</p><p>　　函數(shù)double postfix_exp(char *A)修改前

77、后對(duì)比</p><p>　　函數(shù)int infix_exp_value(char *infixexp,char *postfixexp)修改前后對(duì)比</p><p><b>　　七、課程設(shè)計(jì)總結(jié)</b></p><p>　　通過(guò)這一周的課程設(shè)計(jì)，模擬簡(jiǎn)單計(jì)算器算法有了初步的了解。這次實(shí)驗(yàn)雖然時(shí)間不長(zhǎng)，但是，我還是收獲了許多，首先，要完成一個(gè)課程

78、設(shè)計(jì)師需要我們有嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和扎實(shí)的理論知識(shí)作為基礎(chǔ)和后盾的；其次，還要將理論知識(shí)與實(shí)際課題相結(jié)合，融會(huì)貫通。雖然我們之前對(duì)數(shù)據(jù)結(jié)構(gòu)和C語(yǔ)言的聯(lián)合使用并不熟悉，但通過(guò)老師的詳細(xì)講解和指導(dǎo)、及同學(xué)的互相幫助，最終完成了本次課程設(shè)計(jì)。在這次課程設(shè)計(jì)中，我們還存在著有待改進(jìn)和完善的地方，還需要我們更加深入的去學(xué)習(xí)和了解這方面的知識(shí)，用更加完善的知識(shí)儲(chǔ)備和自己的思考能力相結(jié)合，相信能夠?qū)⒋舜握n程設(shè)計(jì)做的更好，也能更好的提高自己的綜合素質(zhì)和能力