數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---用兩種方式實現(xiàn)表達式自動計算

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：17 大小：293.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　一、設(shè)計思想　　（一）中綴轉(zhuǎn)后綴的設(shè)計思想　　設(shè)計一個能實現(xiàn)表達式自動求值計算，算術(shù)表達式由操作數(shù)、算符和括號組成。由于運算符的優(yōu)先級不同還要考慮括號。所以表達式不可能一直的從左到右進行，所以就借助棧來實現(xiàn)這個表達式的求值。　　首先要把算術(shù)表達式變換成與

2、之等值的無括號表達式，也就是中綴轉(zhuǎn)后綴，它也是這個算法的關(guān)鍵。設(shè)計兩個棧，一個為字符型的，存放運算符，用以將算術(shù)表達式變成無括號的表達式；另一個浮點型的，存放操作數(shù)，用以對無符號的表達式進行求值。我們要假設(shè)運算符的優(yōu)先級：( ) , * /, + - 。首先將一左括號‘(’入棧，作為棧底元素；接著從左到右對算術(shù)表達式進行掃描。每次讀一位，若遇到左括號‘（’，則進棧；若遇到的是操作數(shù)，則立即輸出；若又遇到運算符，如果它的優(yōu)先級比棧頂元素

3、的優(yōu)先級數(shù)高的話，則直接進棧，否則輸出棧頂元素，直到新的棧頂元素的優(yōu)先級數(shù)比它低的，然后將它壓棧；若遇到是右括號‘）’，則將棧頂?shù)倪\算符輸出，直到棧頂?shù)脑貫椤ā缓?，左右括號互相底消；到設(shè)計的結(jié)束標志的時候表示表達式已經(jīng)掃描完畢，表達式已經(jīng)全部輸入，將棧中的運算符全部輸出，刪除棧底的左括號。以上完成了中綴表達式轉(zhuǎn)后綴表達式，輸出無括號的后綴表達式。　　讀后綴表達式，若遇數(shù)值，操作數(shù)進棧；若

4、遇運算符，讓操作數(shù)棧的棧頂和次棧頂依次出棧并與此運算符進行運算，運算結(jié)果入操作數(shù)棧；重復(fù)這個步驟，直到遇到結(jié)束標志，則此時棧中的結(jié)果便是所求的后綴表達式的值，接著輸出結(jié)果。以上就是設(shè)計這個算法的主要的思想。　　(二) 直接計算的設(shè)計思想　　直接計算其實跟上一個相似，它是在上面掃兩遍的思想進行修改的得來。　　首先，

5、要建立兩個棧，一個為字符型的，存放運算符，另一個浮點型的，存放操作數(shù)，我們開始對表達式進行掃描。首先要確定運算符的優(yōu)先級：（、）、*、/、+、-。如果掃描到的是數(shù)字符號，把它們轉(zhuǎn)換成浮點型數(shù)據(jù)或其他可運算的數(shù)據(jù)類型，存入操作數(shù)棧中。如果掃描到的是運算符號，第一個運算符進棧，遇到‘（’存入運算符棧中，我們按照第一種算法的方法將表達式依次掃描。只不過不同的是，當每取得的一個運算符的時候，都要與棧頂?shù)倪\算符進行比較，如果它的優(yōu)先級小于棧頂運算

6、符優(yōu)先級時，取出棧頂運算符并從操作數(shù)棧中取棧頂兩個數(shù)進行運算，得到的結(jié)果則要存回操作數(shù)棧，就這樣邊掃描邊比較，再進行計算。遇到“）”對運算符的處理相同。掃描結(jié)束后，把運算符棧的元素和操作數(shù)棧里的數(shù)進行運算。每次的運算結(jié)果再放入操作數(shù)棧，一直到計算到運算符?？?。最后操作數(shù)棧的棧頂留下的操作數(shù)即表達式的計算結(jié)果。以上就是直接計算表達式的思路。　　二、算法流程圖&

7、lt;/p>　?。ㄒ唬┲芯Y轉(zhuǎn)后綴算法的流程圖　　圖1中綴轉(zhuǎn)后綴算法的流程圖　　流程圖說明：該流程圖分兩部分成，第一部分是中綴轉(zhuǎn)后綴部分，第二部分是用于后綴表達式求值的。　　（二）直接計算算法的流程圖　　圖2接計算算法的流程圖

8、　　流程圖說明：該流程圖進過圖1 改進得到，只是缺少中綴轉(zhuǎn)后綴的部分。　　三、源代碼　　下面給出的是用中綴轉(zhuǎn)后綴算法實現(xiàn)的程序的源代碼：　　#include <stdio.h>　　#define N

9、50　　typedef struct StackArray{　　float data[N];　　int top;　　}StackArray; /*定義操作數(shù)棧*/<

10、;p>　　typedef struct StackChar{　　char data[N];　　int top;　　}StackChar; /*定義操作符棧*/

11、　StackArray *InitNum() /*初始化數(shù)值棧*/　　{　　StackArray *p = (StackArray *)malloc(sizeof(StackArray)); /*取一段內(nèi)存賦予數(shù)值棧*/　　p-&

12、gt;top=-1;　　return p; /*返回*/　　}　　StackChar *InitChar() /*初始化操作符棧*/　　{

13、StackChar *p=(StackChar *)malloc(sizeof(StackChar)); /*取一段內(nèi)存賦予數(shù)值棧*/　　p->top=-1;　　return p;　　}

14、　int PushNum(StackArray *p,float value) /*定義入棧函數(shù)*/　　{　　if(p->top<50-1)　　{　　p->top+=1;&l

15、t;/p>　　p->data[p->top]=value; /*棧頂*/　　return 1;　　}　　else&

16、lt;b>　　{　　return 0;　　}　　}　　int PushChar(StackChar *p,char value)

17、 /*操作符入棧*/　　{　　if(p->top<50-1)　　{　　p->top+=1;　　p->data[p->top

18、]=value; /*入棧為棧頂*/　　return 1;　　}　　else　　{<p&

19、gt;　　return 0; /*返回值*/　　}　　}　　int PopNum(StackArray *p,float *value) /*操作數(shù)出棧*/　　{<

20、/b>　　if(p->top>=0) /*判斷棧是否為空*/　　{　　*value=p->data[p->top];　　p->top-=1;

21、;　　}　　return 1;　　}　　int PopChar(StackChar *p,char *q) /*操作符出棧函數(shù)*/　　{

22、　　if(p->top>=0) /*定義操作符棧*/ 　　{　　*q=p->data[p->top];　　p->top-=1;　　}<

23、;/b>　　return 1;　　}　　float VisitNum(StackArray *p) /*定義數(shù)值棧遍歷函數(shù)*/　　{

24、;　　if(p->top!=-1)　　return p->data[p->top];　　else return 0;　　}　　char visitChar(StackChar *p) /*定

25、義操作符棧遍歷函數(shù)*/　　{　　if(p->top!=-1)　　return p->data[p->top];　　else return 0;　　}<

26、/b>　　int level(char c) /*優(yōu)先級*/　　{　　switch(c)　　{</p&

27、gt;　　case '#': return 0; /*#的優(yōu)先級*/　　case '+':return 1;　　case '-':return 1; /* ‘-‘的優(yōu)先級*/　　case '*':return 2;</

28、p>　　case '/':return 2;　　case '(':return 3; /*（優(yōu)先級*/　　default : return -1;　　}

29、　　}　　int strLen(char *L) /*字符串長度函數(shù)*/　　{　　int i;　　for(i=0;L[i]!='\0';i++); /*循

30、環(huán)條件*/　　if(L[0]=='-'||L[0]=='+')　　{ 　　i=i-1;　　}

31、　　return i;　　}　　float Compute(float a,char c,float b) /*計算*/　　{<b&

32、gt;　　switch(c)　　{　　case '+':return a+b; /*加號的運算*/　　case '-':return a-b;　　case '*'

33、;:return a*b; /*乘號的運算*/　　case '/':return a/b; /*除號的運算*/　　default : return -1;　　}　　}&

34、lt;/p>　　void main()　　{　　StackArray *data;　　StackChar *op;　　int i,j=0;　　fl

35、oat n;　　float result,opA,opB;　　char opChar;　　char array[N];　　char *ptarray=NULL; /*定義指針*/　　float houz

36、hui[N];　　printf("Please enter a data:\t");　　while((scanf("%s",array))!=EOF) /*循環(huán)條件*/　　{　　op=I

37、nitChar();　　data=InitNum();　　PushChar(op,'#');　　array[strLen(array)]='#'; /*結(jié)束標志*/　　ptarray=array;

38、;　　for(i=0;i<strLen(ptarray);i++) /*循環(huán)條件*/　　{　　if(array[i]>=48&&array[i]<=57||array[i]=='.') /*判斷數(shù)值　　{&

39、lt;/b>　　double weight=0.1;　　int flag=0; /*定義變量*/　　float n=0; /*定義變量*/　　n=array[i]-48;　　while(array[i+1]>

40、;=48&&array[i+1]<=57||array[i+1]=='.') /*判定數(shù)值*/　　{　　if(array[i+1]=='.') /*小數(shù)*/

41、　　flag=1;　　else　　{　　if(flag==0)n=n*10+array[i+1]-48; /*整數(shù)化浮點數(shù)*/

42、　　else　　{　　n=n+(array[i+1]-48)*weight; /*小數(shù)化浮點數(shù)*/　　weight*=0.1; /*小數(shù)位權(quán)*/

43、　　}　　}　　i++;　　}　　houzhui[j]=n;<p&g

44、t;　　j++;　　}　　else　　{　　if(array[i]=='#')

45、 /*結(jié)束標志*/　　{　　while(visitChar(op)!='#') /*對操作符棧遍歷*/　　{　　PopChar(op,&opChar);

46、　　houzhui[j]=opChar; /*出棧入數(shù)組*/　　j++;　　}　　}<

47、b>　　else　　{ 　　if(level(array[i])>level(visitChar(op))||　　visitChar(op)=='(') /*判斷優(yōu)先級*/<

48、/p>　　{　　PushChar(op,array[i]); /*入棧*/　　}　　else<p&

49、gt;　　{　　if(array[i]==')') /*遇見字符‘）’*/　　{　　while(visitChar(op)!='(')

50、 /*出戰(zhàn)到‘（’*/　　{　　PopChar(op,&opChar);　　houzhui[j]=opChar;j++; /*操作符入數(shù)組*/　　}

51、 　　PopChar(op,&opChar);　　}else　　{　　while(level(array[i

52、])<=　　level(visitChar(op))) /*優(yōu)先級*/　　{　　PopChar(op,&opChar);　　houzhui[j]=opChar; /*出棧*/<p&

53、gt;　　j++;　　}　　PushChar(op,array[i]); /*運算符進棧*/　　}　　}</p

54、>　　}　　} 　　}　　for(j=0;houzhui[j]!='\0';j++)　　{&

55、lt;/b>　　if((char)houzhui[j]=='+'||(char)houzhui[j]=='-'||　　(char)houzhui[j]=='*'||(char)houzhui[j]=='/') /*類型轉(zhuǎn)換*/<b&g

56、t;　　{　　printf("%2c",(char)houzhui[j]); /*輸出一個運算符*/　　PopNum(data,&opA);　　PopNum(data,&opB);　　resu

57、lt=Compute(opB,(char)houzhui[j],opA); /*調(diào)用函數(shù)*/　　PushNum(data,result); /*結(jié)果入棧*/　　}　　else</p&g

58、t;　　{　　PushNum(data,houzhui[j]);　　printf("%8f",houzhui[j]) /*輸出后綴表達式*/;　　}<

59、;b>　　}　　printf("\nthe Result is:%.2f\n\n",result); /*輸出結(jié)果*/　　}　　}　　下面給出

60、的是用直接計算算法實現(xiàn)的程序的源代碼：　　#include <stdio.h>　　#define N 50　　typedefstructlistStack　　{　　float da

61、ta[N];　　int top;　　}listStack; /*定義存儲操作數(shù)的棧*/　　typedefstructopStack<

62、b>　　{　　char data[N];　　int top;　　}opStack; /*用于定義存儲操作符號的棧*/　　li

63、stStack *InitNum() /*初始化數(shù)值棧*/　　{　　listStack *p=(listStack *)malloc(sizeof(listStack)); /*取一段內(nèi)存賦予數(shù)值棧*/<p

64、>　　p->top = -1; /*定義棧底*/　　return p;　　}　　opStack *InitChar()

65、 /*初始化操作符棧*/　　{　　opStack *p=(opStack *)malloc(sizeof(opStack)); /*取一段內(nèi)存賦予操作符棧*/　　p->top =-1;&l

66、t;p>　　return p;　　}　　intPushNum(listStack *p,float value) /*定義入棧函數(shù)*/　　{</p

67、>　　if(p->top<N-1)　　{　　p->top+=1;　　p->data[p->top]=value; /*入棧的數(shù)值為棧頂元素*/&l

68、t;p>　　return 1;　　}　　else　　{　　return 0; &l

69、t;p>　　}　　}　　intPopNum(listStack *p,float *a) /*定義數(shù)值出棧函數(shù)*/　　{

70、　　if(p->top>=0) /*判定棧不為空*/　　{　　*a=p->data[p->top];　　p->top-=1;&l

71、t;p>　　}　　return 1;　　}　　float VisitNum(listStack *p) /*定義數(shù)值棧遍歷函數(shù)*/

72、　　{　　if(p->top!=-1) /*判定棧是否為空*/　　return p->data[p->top];　　else ret

73、urn 0;　　}　　void PushChar(opStack *p,char a) /* 定義操作符入棧函數(shù)*/　　{　　if(p-&g

74、t;top<N-1)　　{　　p->top+=1;　　p->data[p->top]=a; /*入棧字符為棧頂元素*/　　}<

75、;/b>　　else;　　}　　intPopChar(opStack *p,char *a) /*定義操作符出棧函數(shù)*/<b&g

76、t;　　{　　if(p->top>=0) /*判定棧不為空*/　　{　　*a=p->data[p->top];

77、　　p->top-=1;　　}　　return 1;　　}　　char visitChar(opStack *p)

78、 /*定義操作符棧遍歷函數(shù)*/　　{　　if(p->top!=-1)　　return p->data[p->top]; /*返回棧頂?shù)闹?/

79、　　else return 0;　　}　　intstrLen(char *L) /*計算字符串長度*/　　{<

80、p>　　inti;　　for(i=0;L[i]!='\0';i++); /*循環(huán)條件的判定*/　　if(L[0]=='-'||L[0]=='+')<

81、;b>　　{ 　　i=i-1;　　}　　returni;　　}

82、　　int level(char c) /*符號的優(yōu)先級*/　　{　　switch(c)　　{<

83、/p>　　case '#': return 0;　　case '+':return 1;　　case '-':return 1;　　case '*':return 2;　　case

84、 '/':return 2;　　case '(':return 3;　　default : return -1;　　}　　}

85、;　　float Compute(float a,charch,float b) /*數(shù)據(jù)運算*/　　{　　switch(ch) 　　{

86、case '+':return a+b; /*返回加號數(shù)值運算*/　　case '-':return a-b; /*返回減號數(shù)值運算*/　　case '*':return a*

87、b;　　case '/':return a/b; /*返回除號數(shù)值運算*/　　default :return -1;　　}　　}<

88、;/b>　　void main()　　{　　listStack *data; /*定義操作數(shù)棧，由指針data指出*/　　opStack *op;</p&

89、gt;　　inti; /*對變量進行聲明*/　　float n;　　floatresult,opA,opB;　　char operand[2],opCh

90、ar; /*定義字符型數(shù)組和字符變量*/　　char array[N];　　char *ptarray=NULL; /*定義字符型指針*/　　printf("Please

91、 enter a data:\t");　　while((scanf("%s",array))!=EOF) /*判斷循環(huán)的條件*/　　{　　op=InitChar();　　da

92、ta=InitNum();　　PushChar(op,'#');　　array[strLen(array)]='#'; /*將字符#賦予數(shù)組最后*/　　ptarray=array;

93、for(i=0;i<strLen(ptarray);i++) /*判定循環(huán)的條件*/　　{　　if(array[i]>=48&&array[i]<=57||　　array[i]=='.'

94、) /*判斷值*/　　{　　double weight=0.1;　　int flag=0; /*定義整形變量flag*/

95、　　float n=0; /*定義浮點型變量*/　　n=array[i]-48;　　while(array[i+1]>=48&&array[i+1]<=57||　　array[i+1]=='.')

96、 /*判定數(shù)值*/　　{　　if(array[i+1]=='.') 　　flag=1;/*讀到小數(shù)點*/　　else&l

97、t;p>　　{　　if(flag==0)n=n*10+array[i+1]-48; /*將整數(shù)部分字符串轉(zhuǎn)化為實數(shù)*/　　else　　{　　n=n+(

98、array[i+1]-48)*weight; /*將表示小數(shù)部分的字符也轉(zhuǎn)化過來*/　　weight*=0.1; /*weight為小數(shù)位權(quán)*/　　}　　}<

99、;b>　　i++;　　}　　PushNum(data,n); /*將數(shù)值進棧*/　　}　　else</

100、b>　　{　　if(array[i]=='#') /*遇見字符#*/　　{　　while(visitChar(op)!=&

101、#39;#') /*對操作符棧進行遍歷*/　　{　　PopChar(op,&opChar); /*字符出棧*/　　PopNum(data,&opA);　　PopNum(data,&

102、amp;opB); /*數(shù)出棧*/　　result=Compute(opB,opChar,opA); /*調(diào)用運算函數(shù)*/　　PushNum(data,result);　　}

103、}　　else　　{ 　　if(level(array[i])>level(visitChar(op))||　　visitChar(op)=='(')

104、 /*判斷操作符的優(yōu)先級高低*/　　{　　PushChar(op,array[i]); /*操作符進棧*/　　}　　else</

105、p>　　{　　if(array[i]==')') /*當操作符為)時*/　　{　　while(visitChar(op)!='(') /*遍

106、歷操作符棧*/　　{　　PopChar(op,&opChar);　　PopNum(data,&opA);　　PopNum(data,&opB); /*從數(shù)值棧輸出一個值*/

107、　　result=Compute(opB,opChar,opA);　　PushNum(data,result); /*結(jié)果放回棧里*/　　} 　　PopChar(op,&opChar

108、); /*輸出操作符*/　　}　　else　　{　　while(level(array[i])<=level(visitChar(op))) /

109、*判斷操作符的優(yōu)先級高低*/　　{　　PopChar(op,&opChar);　　PopNum(data,&opA); /*從數(shù)值棧輸出數(shù)值*/　　PopNum(data,&opB);

110、;　　esult=Compute(opB,opChar,opA); /*調(diào)用運算函數(shù)*/　　PushNum(data,result); /*將運算結(jié)果入棧*/　　}　　PushChar(op,array[i]); /*將操作符入棧*

111、/　　}　　}　　}　　} 　　}&

112、lt;/p>　　printf("the Result is:%.6f\n\n",result); /*輸出掃描一遍的運算結(jié)果*/　　}　　}　　四、運行結(jié)果<

113、/b>　?。ㄒ唬┲芯Y轉(zhuǎn)后綴算法的運行結(jié)果：　　圖 3中綴轉(zhuǎn)后綴算法的運行結(jié)果　　（二）直接計算算法的運行結(jié)果：　　圖 4 直接計算算法的運行結(jié)果　　五、遇到的問題及解決　　這部分我主

114、要遇到了如下兩個問題，其內(nèi)容與解決方法如下所列：　　問題1: 　　在遇到小數(shù)點處理的問題上，雖然說處理小數(shù)點的方法不是唯一的，但我在處理的時候只能計算一位小數(shù)，如果輸入的是兩位的話，計算結(jié)果的時候它就把一位小數(shù)后面的數(shù)據(jù)全丟了。　　解決方法: </b&

115、gt;　　在輸出后綴表達式的時候可以看到棧里存的數(shù)據(jù)最多只帶一位小數(shù)，所以結(jié)果也只能出現(xiàn)一位小數(shù)。因為在處理小數(shù)的時候我是讓小數(shù)點后面的數(shù)乘以0.1，再加上前面的。但如果是兩位的話，那么最后的那一個是要乘以0.01的，也就是乘以0.1的自乘，所以在處理小數(shù)時我加了自乘的這行代碼，運行的結(jié)果才真確的出來了。 　　問題2: </b&g

116、t;　　無論輸入什么表達式，不知道結(jié)果為什么始終是‘0.00‘，運行還是行的，有的時候程序只是按照掃到最后的一個運算符來執(zhí)行。　　圖 5 運行出錯　　解決方法: 　　剛開始不知道哪兒出錯了，就瞎找

117、那些有可能會出現(xiàn)錯的地方，比如：能從圖中直接看出來，沒有后綴表達式；計算結(jié)果也是錯誤的；還有可能是哪個函數(shù)調(diào)用時出了錯。隨后就從最簡單的函數(shù)調(diào)用出錯的問題開始檢查，沒有發(fā)現(xiàn)什么明顯的錯誤，就放棄了這個問題，接著就是計算有沒有出現(xiàn)簡單的錯誤，因為它比較于中綴轉(zhuǎn)后綴要簡單一些，就開始試，單獨的對這一段代碼試，結(jié)果還是沒發(fā)現(xiàn)什么錯誤，最后就剩下最難的中綴轉(zhuǎn)后綴的問題了，如果這個也沒有錯，那就不知道哪兒出錯了，就開始對它調(diào)試，看了兩個小時也沒

118、找出來什么錯誤。以后才找到那兒出了漏洞，原來缺少一句賦值語句“houzhui[j]=n；”就成這樣了，這個錯誤告訴我一點點的小錯誤也能導(dǎo)致整個程序的錯誤。　　六、心得體會　　通過這次的作業(yè)我充分的認識到了自己的不足，特別是對寫程序代碼這方面，一個程序從算法到用程序把它實現(xiàn)出來，這一整個過程是很不容易的，你懂得它的算法

119、，不一定就能寫的出來，通過這次我也深深的了這一點。對于一個新手來說，小的錯誤出現(xiàn)的太多，而且一個小的錯誤就能讓我束手無策，因為想不通錯在哪，所以就一直在亂改，邏輯錯誤就更難了，有時候程序運行語法沒有錯誤，但只要輸入表達式計算結(jié)果時，出來的結(jié)果要不是錯的，要不就不出現(xiàn)結(jié)果，這種錯的原因更難找。感覺難的原因可能就是平時少練習(xí)，代碼量也是積累很少的，這樣我們尋找程序的錯誤覺得很難，修改過來就更難了。但是運行的正確結(jié)果出來的時候，覺得有點興奮。

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---用兩種方式實現(xiàn)表達式自動計算

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---用兩種方式實現(xiàn)表達式自動計算

文檔簡介

溫馨提示

最新文檔

評論

免費下載