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

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

2、用棧來(lái)進(jìn)出運(yùn)算的數(shù)字將后綴表達(dá)式的值求出即可。3、 數(shù)據(jù)結(jié)構(gòu)定義一般表達(dá)式的長(zhǎng)度不會(huì)過(guò)長(zhǎng)所以將順序棧的容量設(shè)為100已經(jīng)算是比較大了具體數(shù)據(jù)結(jié)構(gòu)如下：# define maxsize 100typedef double datatype1;typedef char datatype2;typedef struct stack1 datatype1 data1maxsize; int top1;/*棧頂元素*/seqstack1,*pseqstack1; /*順序棧*/typedef struct stack2 datatype2 data2maxsize; int top2;/*棧頂元素*/s

3、eqstack2,*pseqstack2; /*順序棧*/4、 系統(tǒng)功能模塊介紹（1） 判斷字符是否為操作數(shù)函數(shù) int isnum(char)當(dāng)輸入表達(dá)式時(shí)要利用棧對(duì)表達(dá)式中的數(shù)字和符號(hào)進(jìn)行進(jìn)棧出棧，因此要判斷表達(dá)式中的內(nèi)容是操作數(shù)、運(yùn)算符還是界限符，給出相關(guān)信息。（2） 求運(yùn)算符優(yōu)先級(jí)函數(shù) int priority(char ) 對(duì)輸入的表達(dá)式中的內(nèi)容，若為運(yùn)算符和界限符則要判斷其優(yōu)先級(jí)已完成其計(jì)算的先后順序。（3） 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式函數(shù) int infix_exp_value(char *,char *) 我們平時(shí)使用的為中綴表達(dá)式，但若利用棧則利用后綴表達(dá)式比較容易計(jì)算，因此

4、要將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，具體算法步驟如下：count=0，初始化運(yùn)算符棧s，將結(jié)束符# 加入運(yùn)算符棧s中。讀表達(dá)式字符=w。當(dāng)棧頂為# 并且w也是# 時(shí)結(jié)束；否則循環(huán)做下列步驟： 如果w是操作數(shù)判斷若count=0直接輸出,讀下一個(gè)字符=w;轉(zhuǎn)。若 count!=0 追加字符, 讀下一個(gè)字符=w, 轉(zhuǎn)。 w若是運(yùn)算符，則：count=1; 如果棧頂為（并且w為）則（出棧不輸出，讀下一個(gè)字 符=w，轉(zhuǎn)。 如果棧頂為（或者棧頂優(yōu)先級(jí)小于w優(yōu)先級(jí)，則w入棧，讀下 一個(gè)字符=w，轉(zhuǎn)。否則：從運(yùn)算符棧中出棧并輸出，轉(zhuǎn)（4） 后綴表達(dá)式的求值函數(shù) double postfix_exp(char *

5、)使用一個(gè)操作數(shù)棧，當(dāng)從左到右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中保存，如果操作數(shù)不止一位，則保存在operand中，遇到下一個(gè)操作數(shù)時(shí)，執(zhí)行operand=operand*10+(ch-0)，便可將操作數(shù)轉(zhuǎn)化為數(shù)字。每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果在入棧，直到整個(gè)表達(dá)式結(jié)束，這時(shí)送入棧頂?shù)闹稻褪墙Y(jié)果。5、 程序清單# include # include # include # define maxsize 100typedef double datatype1;typedef char datatype2;typedef struct stack1 dat

6、atype1 data1maxsize; int top1;/*棧頂元素*/seqstack1,*pseqstack1; /*順序棧*/typedef struct stack2 datatype2 data2maxsize; int top2;/*棧頂元素*/seqstack2,*pseqstack2; /*順序棧*/*棧的初始化*/pseqstack1 init_seqstack1(void) pseqstack1 S; S=(pseqstack1)malloc(sizeof(pseqstack1); if(S) S-top1=-1; return S;pseqstack2 init_se

7、qstack2(void) pseqstack2 S; S=(pseqstack2)malloc(sizeof(pseqstack2); if(S) S-top2=-1; return S;/*判斷?？?/int empty_seqstack1(pseqstack1 S) if(S-top1=-1) return 1; else return 0;int empty_seqstack2(pseqstack2 S) if(S-top2=-1) return 1; else return 0;/*X入棧*/int push_seqstack1(pseqstack1 S,datatype1 X) i

8、f(S-top1=maxsize-1) printf(棧滿，無(wú)法入棧！n); return 0; else S-top1+; S-data1S-top1=X; return 1; int push_seqstack2(pseqstack2 S,datatype2 X) if(S-top2=maxsize-1) printf(棧滿，無(wú)法入棧！n); return 0; else S-top2+; S-data2S-top2=X; return 1; /*X出棧*/int pop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S)

9、return 0; else *X=S-data1S-top1; S-top1-; return 1; int pop_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0; else *X=S-data2S-top2; S-top2-; return 1; /*求棧頂元素*/int gettop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0; else *X=S-data1S-top1; return 1;int gett

10、op_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0; else *X=S-data2S-top2; return 1;/*判斷字符是否為操作數(shù)。若是返回1，否則返回0*/int isnum(char c) if(c=0 & cA*/ S=init_seqstack1();/*初始化棧*/ while(ch!=#)/*遇到元素!=#時(shí)*/ if(isnum(ch)/*判斷ch是否為數(shù)字字符,計(jì)算出操作數(shù)*/ operand=operand*10+(ch-0); else/*否則*/ if(operand)p

11、ush_seqstack1(S,operand);/*當(dāng)前字符不是數(shù)字,操作數(shù)結(jié)束,要入棧*/operand=0;if(ch!= & ch!= )pop_seqstack1(S,&b);/*運(yùn)算符ch后的操作數(shù)出棧存入b*/pop_seqstack1(S,&a);/*運(yùn)算符ch前的操作數(shù)出棧存入a*/switch(ch)/*求 a ch b=? ,將結(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_seqst

12、ack1(S,c);/*將c壓入棧中*/ ch=*A+;/*指針向下移動(dòng)一位*/ /*遇到#循環(huán)結(jié)束*/ gettop_seqstack1(S,&result);/*此時(shí)棧頂元素即為計(jì)算結(jié)果result*/ return result;/*優(yōu)先級(jí)判斷函數(shù)*/int priority(char op)switch(op)case #: return 1;case ): return 2;case +: case -: return 3;case *: case /: return 4;case (: return 5;default : return 0; /*將指針infixexp指向的中綴表

13、達(dá)式轉(zhuǎn)換為指針postfixexp指向的后綴表達(dá)式*/int infix_exp_value(char *infixexp,char *postfixexp)pseqstack2 S;/*定義棧S*/int count=0;char w;/*存放讀取到的表達(dá)式(infixexp)的字符*/char c;/*存放棧頂元素*/char topelement;/*存出棧元素*/S=init_seqstack2();/*初始化棧*/if(!S)/*棧的初始化判斷*/printf(棧初始化失敗!);return 0;push_seqstack2(S,#);/*將結(jié)束符# 加入運(yùn)算符棧S中*/w=*inf

14、ixexp;/*讀表達(dá)式字符=w*/while(gettop_seqstack2(S,&c),c)!=#|w!=#)/*棧頂元素不等于#或w不等于#時(shí)循環(huán)*/if(isnum(w)/*判斷w是否為操作數(shù),若是直接輸出,讀下一個(gè)字符=w,轉(zhuǎn)*/if(count)*postfixexp=;postfixexp+;count=0;*postfixexp=w;postfixexp+;w=*(+infixexp);else/*w若是運(yùn)算符分類如下*/count=1;if( (gettop_seqstack2(S,&c),c)=( & w=) )/*如果棧頂為(并且w為)則(出棧不輸出,讀下一個(gè)字符=w,

15、轉(zhuǎn)*/pop_seqstack2(S,&topelement); /*將(出棧存入topelement*/w=*(+infixexp);elseif( (gettop_seqstack2(S,&c),c)=( | priority( (gettop_seqstack2(S,&c),c) ) w，轉(zhuǎn)*/push_seqstack2(S,w);w=*(+infixexp);else/*否則*/*從運(yùn)算符棧中出棧并輸出,轉(zhuǎn)*/pop_seqstack2(S,&topelement);*postfixexp=topelement;postfixexp+;*postfixexp=#;/*在指針postf

16、ixexp指向的后綴表達(dá)式結(jié)尾追加字符#*/*(+postfixexp)=0;/*在指針postfixexp指向的后綴表達(dá)式最后追加結(jié)束符0*/return 1;/*主函數(shù)*/int main() int i=0;char Amaxsize;char Bmaxsize;printf(請(qǐng)輸入表達(dá)式,如:11+22#,必須以#號(hào)結(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);printf(A=%sn,A);

17、printf(B=%sn,B);printf(上式的結(jié)果為: );printf(%gn,postfix_exp(B);return 0; getch();6、 運(yùn)行與調(diào)試分析等（6.1）、運(yùn)行與調(diào)試（1）、先輸入： 3+5*2# 后按回車求值，結(jié)果應(yīng)為：13（2）、先輸入： 1+2*(9+7)-4/2# 后按回車求值，結(jié)果應(yīng)為：31（3）、先輸入： 15+3-2+(9/4)# 后按回車求值，結(jié)果應(yīng)為：18.25（4）、先輸入： 1+3-2+(4*5/10)-2# 后按回車求值，結(jié)果應(yīng)為：2（5）、先輸入：23+(12*3-2)/4+34*5/7)+108/9# 后按回車求值，結(jié)果應(yīng)為：67.785714（6.2）、分析根據(jù)以上結(jié)果可以知道本程序正確，本程序中int isnum(char c)double postfix_exp(char *A)int priority(char op)int infix_exp_value(char *infixexp,char *postfixex