數(shù)據(jù)結(jié)構(gòu)表達(dá)式的值課程設(shè)計(jì)

1、河北科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告學(xué)生姓名： 學(xué) 號： 專業(yè)班級： 課程名稱： 數(shù)據(jù)結(jié)構(gòu)（c語言版 學(xué)年學(xué)期： 2 014 2 0 15 學(xué)年第 二 學(xué)期 指導(dǎo)教師： 白云飛 2 0 15 年 7 月課程設(shè)計(jì)成績評定表學(xué)生姓名學(xué) 號成績專業(yè)班級軟件121起止時間2015.6-2015.7設(shè)計(jì)題目表達(dá)式的值驗(yàn)收內(nèi)容課程設(shè)計(jì)小組驗(yàn)收結(jié)果：硬件設(shè)計(jì)：優(yōu)秀良好中等及格需努力程序設(shè)計(jì)：優(yōu)秀良好中等及格需努力實(shí)驗(yàn)結(jié)果：優(yōu)秀良好中等及格需努力課程設(shè)計(jì)個人驗(yàn)收結(jié)果：操作能力：優(yōu)秀良好中等及格需努力軟件理解：優(yōu)秀良好中等及格需努力硬件理解：優(yōu)秀良好中等及格需努力指導(dǎo)教師： 年 月 日目 錄1、 題目的內(nèi)容與要求

2、42、 需求分析 43、 概要設(shè)計(jì) 44、 詳細(xì)設(shè)計(jì) 55、 源代碼 76、 運(yùn)行結(jié)果與分析 167、 收獲與體會 161、 題目的內(nèi)容即要求從文件讀取表達(dá)式，判斷表達(dá)式是否合理，將表達(dá)式轉(zhuǎn)換成后綴形式，按后綴表達(dá)式求值；題目涉及加減乘除，帶括弧的混合運(yùn)算；隨時可以退出。2、 需求分析程序先從文本文件中讀取表達(dá)式，然后利用棧設(shè)計(jì)一個程序，該程序能夠用于表達(dá)式求值，程序?qū)⒆x入的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后按后綴表達(dá)式進(jìn)行計(jì)算，輸出結(jié)果。  本程序具有檢測表達(dá)式語法是否正確的功能，如果表達(dá)式出現(xiàn)錯誤的時候，程序會提示操作人員執(zhí)行的表達(dá)式不合理，語法是不能執(zhí)行的。語法正常的情

3、況下，程序可以實(shí)現(xiàn)了加、減、乘、除以及帶括號的基本運(yùn)算。程序在執(zhí)行表達(dá)式的時候，先檢查表達(dá)式是否合理，不合理則輸出表達(dá)式不符合要求，合理則將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，然后則對表達(dá)式求值，輸出結(jié)果。3、 概要設(shè)計(jì) 本程序選用的是線性表數(shù)據(jù)結(jié)構(gòu)。它按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)的數(shù)據(jù)被壓入棧最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候才棧頂開始探出數(shù)據(jù)。 程序采用的是順序存儲結(jié)構(gòu)，可以將邏輯上相鄰的數(shù)據(jù)元素放在物理上相鄰的存儲單元里，節(jié)電之間的關(guān)系由存儲單元相鄰的關(guān)系來決定。 選擇線性表結(jié)構(gòu)是因?yàn)槌绦蚴怯脳碓O(shè)計(jì)的，可以將優(yōu)先運(yùn)算的送至棧頂，低級別的運(yùn)算則最后根據(jù)先后進(jìn)棧的順序來執(zhí)行。選擇順序存儲結(jié)構(gòu)是

4、因?yàn)轫樞虼鎯Y(jié)構(gòu)存取數(shù)據(jù)數(shù)度快，占用的存儲空間小。系統(tǒng)的功能模塊劃分：1、Translate()的功能是將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 2、Disp()的功能是輸出后綴表達(dá)式3、Process()的功能是將原表達(dá)式進(jìn)行預(yù)處理，檢查符號是否匹配，轉(zhuǎn)化為中綴式。4、endright的功能是先對表示式的運(yùn)算符進(jìn)行處理，考慮其計(jì)算的優(yōu)先級。5、FindSymbol（）的功能是對表達(dá)式的括號進(jìn)行優(yōu)先處理。6、FindError（）的功能是檢查表達(dá)式是否有語法錯誤。操作之間的調(diào)用關(guān)系：各個函數(shù)是通過主函數(shù)main()來調(diào)用的，當(dāng)程序接受一段表達(dá)式的時候，先通過Process()對整個表達(dá)式做一個運(yùn)算的預(yù)處理

5、，轉(zhuǎn)化為中綴式。FindError（）檢查表達(dá)式是否出現(xiàn)可以執(zhí)行，然后送入FindSymbol（）進(jìn)行處理，帶括號的運(yùn)算優(yōu)先處理，之后endright函數(shù)檢查表達(dá)式的優(yōu)先級，高級的運(yùn)算先進(jìn)行處理。接著Translate()函數(shù)把表達(dá)式轉(zhuǎn)換為后綴式。 Disp()的功能是輸出后綴表達(dá)式。計(jì)算表達(dá)式。最后主函數(shù)輸出計(jì)算結(jié)果。 4、 詳細(xì)設(shè)計(jì) 在計(jì)算機(jī)中，算數(shù)表達(dá)式的計(jì)算通常是通過使用棧來實(shí)現(xiàn)的。所以表達(dá)式求值程序最主要的數(shù)據(jù)結(jié)構(gòu)就是棧。可以使用棧來存儲輸入表達(dá)式的操作符和操作數(shù)。輸入的表達(dá)式是由操作數(shù)和操作符以及改變運(yùn)算次序的括號連接而成的。（1） 本程序通過Disp()的功能是輸出后綴表達(dá)式。

6、將中綴式轉(zhuǎn)化為后綴式，要將遇到的運(yùn)算對象直接放入后綴式的存儲區(qū)。將剛讀入的字符送至操作數(shù)棧，如果遇到運(yùn)算符則送入運(yùn)算符棧。通過棧的先后進(jìn)棧的順序來將操作數(shù)和操作符進(jìn)行出棧，然后輸出后綴表達(dá)式。void Disp() int i; printf(" 后綴表達(dá)式:"); for (i=0;i<=postlength;i+) if (strcmp(,"number")=0) printf("%g ",.val); else printf("%s

7、",); （2） 程序通過FindSymbol（）的功能是對表達(dá)式的括號進(jìn)行優(yōu)先處理。 該函數(shù)使用棧的方法，來解決表達(dá)式中帶括號的進(jìn)行先處理，當(dāng)兩個棧都處于一個優(yōu)先級的是時候，說明表達(dá)式出現(xiàn)左右括號，進(jìn)行優(yōu)先運(yùn)算。對表達(dá)式的括號優(yōu)先處理。int FindSymbol(char str,int pos) int h,k; char wordMAXTOKEN; word0=strpos; word1='0' pos+; if (h=hashtableHash(word)=-1) printf("表達(dá)式中存在不能識別的符號n

8、"); return -1; else if (Leading()=1) if (Kind(h)=RIGHTPAREN) printf("不應(yīng)為右括號n"); return -1; else if (Kind(h)!=BINARYOP) PutToken(h); else if (strcmp(word,"+")=0); else if (strcmp(word,"-")=0) PutToken(hashtableHash(""); else printf(" >>二元運(yùn)算符不正確n

9、"); return -1; else if (Kind(h)=BINARYOP | Kind(h)=RIGHTPAREN) PutToken(h); else printf("二元運(yùn)算符不正確n"); return -1; if (k=Kind(h)=LEFTPAREN) parencount+; else if (k=RIGHTPAREN) if (-parencount<0) printf("太多的右括號n"); return -1; return pos;（3） FindError（）的功能是檢查表達(dá)式是否有語法錯誤。 通過主函數(shù)

10、調(diào)用后，對表達(dá)式進(jìn)行語法差錯。當(dāng)語法出現(xiàn)錯誤時，則通過return()=0,f返回到主函數(shù)，報(bào)告表達(dá)式出錯。輸出結(jié)果，表達(dá)式出錯。當(dāng)表達(dá)式是合理的時候，該函數(shù)運(yùn)行結(jié)束，則停止調(diào)用，進(jìn)入主函數(shù)。實(shí)現(xiàn)下一個函數(shù)的調(diào)用。int FindError(char str,int pos) int h; char wordMAXTOKEN; pos=ExtractWord(str,pos,word); h=hashtableHash(word); if (h!=-1) if (Leading()=1) if (Kind(h)=BINARYOP) printf("二元運(yùn)算符位置不正確n")

11、; return -1; else PutToken(h); else if (Kind(h)!=BINARYOP) printf("應(yīng)為二元運(yùn)算符n"); return -1; else PutToken(h); return pos; else printf(" >>不正確的標(biāo)識符n"); return -1; int FindNumber(char str,int pos) if (Leading()=0) printf("常量位置不正確n"); return -1; else lexicon+tokencount.

12、kind=OPERAND; .val=atof(&strpos); strcpy(,"number"); PutToken(tokencount); for (;isdigit(strpos) | strpos='.'pos+); return pos; 5、 源代碼/*該程序從文本文檔讀取表達(dá)式，并轉(zhuǎn)換為后綴表達(dá)式，再求值 工程文件需附帶一文本文檔*/#include <stdio.h>#include <string.h>#includ

13、e <ctype.h>#include <math.h>#include <stdlib.h>#include<conio.h>#define MAXNAME 7 #define MAXPRIORITY 6 #define MAXTOKEN 100 #define MAXSTACK 100 #define MAXSTRING 101 #define HASHSIZE 101 #define LASTOPERAND 17 typedef double Value_type;typedef enum kind_tag UNARYOP,BINARYOP

14、,OPERAND,LEFTPAREN,RIGHTPAREN,ENDEXPR Kind_type;typedef struct char nameMAXNAME; Kind_type kind; union int pri; Value_type val; info; Token_type;Token_type lexiconMAXTOKEN= "#",ENDEXPR, "(",LEFTPAREN, ")",RIGHTPAREN, "",UNARYOP,6, "abs",UNARYOP,6, &q

15、uot;sqrt",UNARYOP,6, "exp",UNARYOP,6, "ln",UNARYOP,6, "log10",UNARYOP,6, "sin",UNARYOP,6, "cos",UNARYOP,6, "tanh",UNARYOP,6, "+",BINARYOP,4, "-",BINARYOP,4, "*",BINARYOP,5, "/",BINARYOP,5, "

16、%",BINARYOP,5, "",BINARYOP,6; int hashtableMAXTOKEN;int infixMAXTOKEN; int postfixMAXTOKEN; int inlength; int postlength; int parencount; int tokencount; int Hash(char *name) int h=name0 % HASHSIZE; while (1) if (hashtableh=-1) break; else if (strcmp(,name)=0) br

17、eak; else if (name1='0') h+=31; else h+=name1; h%=HASHSIZE; return abs(h); void MakeHashTable() int i; for (i=0;i<HASHSIZE;i+) hashtablei=-1; for (i=1;i<=LASTOPERAND;i+) hashtableHash()=i; Kind_type Kind(int h) return(lexiconh.kind); int Priority(int h) return(lexiconh.inf

18、o.pri); int Leading() int k; if (inlength<=-1) return 1; else return (k=Kind(infixinlength)=LEFTPAREN | k=UNARYOP | k=BINARYOP; void PutToken(int h) inlength+; infixinlength=h; void PutToken1(int h) postlength+; postfixpostlength=h; int ExtractWord(char str,int pos,char *word) int i; char *pw=wor

19、d; for (i=pos;isalpha(stri) | isdigit(stri);i+) *pw+=tolower(stri); *pw='0' return i; int FindError(char str,int pos) int h; char wordMAXTOKEN; pos=ExtractWord(str,pos,word); h=hashtableHash(word); if (h!=-1) if (Leading()=1) if (Kind(h)=BINARYOP) printf("二元運(yùn)算符位置不正確n"); return -1;

20、else PutToken(h); else if (Kind(h)!=BINARYOP) printf("應(yīng)為二元運(yùn)算符n"); return -1; else PutToken(h); return pos; else printf(" >>不正確的標(biāo)識符n"); return -1; int FindNumber(char str,int pos) if (Leading()=0) printf("常量位置不正確n"); return -1; else lexicon+tokencount.kind=OPERAND;

21、 .val=atof(&strpos); strcpy(,"number"); PutToken(tokencount); for (;isdigit(strpos) | strpos='.'pos+); return pos; int FindSymbol(char str,int pos) int h,k; char wordMAXTOKEN; word0=strpos; word1='0' pos+; if (h=hashtableHash(

22、word)=-1) printf("表達(dá)式中存在不能識別的符號n"); return -1; else if (Leading()=1) if (Kind(h)=RIGHTPAREN) printf("不應(yīng)為右括號n"); return -1; else if (Kind(h)!=BINARYOP) PutToken(h); else if (strcmp(word,"+")=0); else if (strcmp(word,"-")=0) PutToken(hashtableHash("");

23、 else printf(" >>二元運(yùn)算符不正確n"); return -1; else if (Kind(h)=BINARYOP | Kind(h)=RIGHTPAREN) PutToken(h); else printf("二元運(yùn)算符不正確n"); return -1; if (k=Kind(h)=LEFTPAREN) parencount+; else if (k=RIGHTPAREN) if (-parencount<0) printf("太多的右括號n"); return -1; return pos;v

24、oid GetToken(int &h) inlength+; h=infixinlength;void GetToken1(int &h) postlength+; h=postfixpostlength; void Translate() int StMAXSTACK;int top=-1; int h,h1; Kind_type type; postlength=-1; inlength=-1; int endright; do GetToken(h); switch(type=Kind(h) case OPERAND: PutToken1(h); break; case

25、 LEFTPAREN: top+; Sttop=h; break; case RIGHTPAREN: h=Sttop;top-; while (top>-1 && Kind(h)!=LEFTPAREN) PutToken1(h); h=Sttop;top-; break; case UNARYOP: case BINARYOP: endright=0; do if (top=-1) endright=1; else if (Kind(Sttop)=LEFTPAREN) endright=1; else if (Priority(Sttop)<Priority(h)

26、endright=1; else if (Priority(Sttop)=Priority(h) && Priority(h)=MAXPRIORITY) endright=1; else h1=h; endright=0; h=Sttop;top-; PutToken1(h); h=h1; while (endright=0); top+;Sttop=h; break; case ENDEXPR: while (top>-1) h=Sttop;top-; PutToken1(h); break; while (type!=ENDEXPR); PutToken1(0); i

27、nt Process(char *instring) int len,pos; inlength=-1; parencount=0; tokencount=LASTOPERAND; len=strlen(instring); instringlen='0' for (pos=0;pos<len;) if (instringpos=' ') pos+; else if (isalpha(instringpos) pos=FindError(instring,pos); else if (isdigit(instringpos) | instringpos=&

28、#39;.') pos=FindNumber(instring,pos); else pos=FindSymbol(instring,pos); if (pos=-1) return 0; if (parencount!=0) printf("左右括號不匹配n"); PutToken(0); return 1; void Disp() int i; printf(" 后綴表達(dá)式:n"); for (i=0;i<=postlength;i+) if (strcmp(,"number"

29、)=0) printf("%g ",.val); else printf("%s ",); Value_type DoBinary(int h,Value_type x,Value_type y) switch(h) case 12: return(x+y); case 13: return(x-y); case 14: return(x*y); case 15: if (y!=(Value_type)0) return(x/y); else printf(" &g

30、t;>除零錯誤n"); break; case 16: if (y!=(Value_type)0) return(fmod(x,y); else printf(" >>除零錯誤n"); break; case 17: return(pow(x,y); default: printf(" >>%d是無效的二元運(yùn)算符n",h); break; Value_type DoUnary(int h,Value_type x) switch(h) case 3: return(-x); case 4:return(abs(x)

31、; case 5: if (x>=0) return(sqrt(x); else printf(" >>負(fù)數(shù)不能開平方n"); break; case 6: return(exp(x); case 7: if (x>0) return(log(x); else printf(" >>負(fù)數(shù)不能求lnn"); break; case 8: if (x>0) return(log10(x); elseprintf(" >>負(fù)數(shù)不能求log10n"); break; case 9: ret

32、urn(sin(x); case 10: return(cos(x); case 11: return(tanh(x); Value_type GetValue(int h) if (Kind(h)!=OPERAND) printf(" >>不是一個操作數(shù)n"); else return(.val);Value_type EvaluatePostfix() Kind_type type; int h; Value_type x,y; double StMAXSTACK; int top=-1; postlength=-1; do Get

33、Token1(h); switch(type=Kind(h) case OPERAND: top+; Sttop=GetValue(h); break; case UNARYOP: x=Sttop; top-;top+; Sttop=DoUnary(h,x);break; case BINARYOP: y=Sttop;top-; x=Sttop;top-; top+; Sttop=DoBinary(h,x,y);break; case ENDEXPR: x=Sttop;top-; if (top>-1) printf(" >>不正確的表達(dá)式n"); break; while (type!=ENDEXPR); return(x); ;void main() char instringMAXSTRING; MakeHashTable(); printf("n");FILE *fp;char *pchBuf;int NLen;fp=fopen("data.txt","r");f