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

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

3、減、乘、除以及帶括號的基本運算。程序在執行表達式的時候，先檢查表達式是否合理，不合理則輸出表達式不符合要求，合理則將中綴表達式轉化為后綴表達式，然后則對表達式求值，輸出結果。3、 概要設計 本程序選用的是線性表數據結構。它按照后進先出的原則存儲數據，先進的數據被壓入棧最后的數據在棧頂，需要讀數據的時候才棧頂開始探出數據。 程序采用的是順序存儲結構，可以將邏輯上相鄰的數據元素放在物理上相鄰的存儲單元里，節電之間的關系由存儲單元相鄰的關系來決定。 選擇線性表結構是因為程序是用棧來設計的，可以將優先運算的送至棧頂，低級別的運算則最后根據先后進棧的順序來執行。選擇順序存儲結構是因為順序存儲結構存取數據

4、數度快，占用的存儲空間小。系統的功能模塊劃分：1、translate()的功能是將中綴表達式轉換為后綴表達式 2、disp()的功能是輸出后綴表達式3、process()的功能是將原表達式進行預處理，檢查符號是否匹配，轉化為中綴式。4、endright的功能是先對表示式的運算符進行處理，考慮其計算的優先級。5、findsymbol（）的功能是對表達式的括號進行優先處理。6、finderror（）的功能是檢查表達式是否有語法錯誤。操作之間的調用關系：各個函數是通過主函數main()來調用的，當程序接受一段表達式的時候，先通過process()對整個表達式做一個運算的預處理，轉化為中綴式。find

5、error（）檢查表達式是否出現可以執行，然后送入findsymbol（）進行處理，帶括號的運算優先處理，之后endright函數檢查表達式的優先級，高級的運算先進行處理。接著translate()函數把表達式轉換為后綴式。 disp()的功能是輸出后綴表達式。計算表達式。最后主函數輸出計算結果。 4、 詳細設計 在計算機中，算數表達式的計算通常是通過使用棧來實現的。所以表達式求值程序最主要的數據結構就是棧。可以使用棧來存儲輸入表達式的操作符和操作數。輸入的表達式是由操作數和操作符以及改變運算次序的括號連接而成的。（1） 本程序通過disp()的功能是輸出后綴表達式。 將中綴式轉化為后綴式，要

6、將遇到的運算對象直接放入后綴式的存儲區。將剛讀入的字符送至操作數棧，如果遇到運算符則送入運算符棧。通過棧的先后進棧的順序來將操作數和操作符進行出棧，然后輸出后綴表達式。void disp() int i; printf( 后綴表達式:); for (i=0;i二元運算符不正確n); return -1; else if (kind(h)=binaryop | kind(h)=rightparen) puttoken(h); else printf(二元運算符不正確n); return -1; if (k=kind(h)=leftparen) parencount+; else if (k=ri

7、ghtparen) if (-parencount不正確的標識符n); return -1; int findnumber(char str,int pos) if (leading()=0) printf(常量位置不正確n); return -1; else lexicon+tokencount.kind=operand; .val=atof(&strpos); strcpy(,number); puttoken(tokencount); for (;isdigit(strpos) | strpos=.;

8、pos+); return pos; 5、 源代碼/*該程序從文本文檔讀取表達式，并轉換為后綴表達式，再求值 工程文件需附帶一文本文檔*/#include #include #include #include #include #include#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;type

9、def enum kind_tag unaryop,binaryop,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, sqrt,unaryop,6, exp,unaryop,

10、6, ln,unaryop,6, log10,unaryop,6, sin,unaryop,6, cos,unaryop,6, tanh,unaryop,6, +,binaryop,4, -,binaryop,4, *,binaryop,5, /,binaryop,5, %,binaryop,5, ,binaryop,6; int hashtablemaxtoken;int infixmaxtoken; int postfixmaxtoken; int inlength; int postlength; int parencount; int tokencount; int hash(char

11、 *name) int h=name0 % hashsize; while (1) if (hashtableh=-1) break; else if (strcmp(,name)=0) break; else if (name1=0) h+=31; else h+=name1; h%=hashsize; return abs(h); void makehashtable() int i; for (i=0;ihashsize;i+) hashtablei=-1; for (i=1;i=lastoperand;i+) hashtablehash(le

12、)=i; kind_type kind(int h) return(lexiconh.kind); int priority(int h) return(.pri); int leading() int k; if (inlength不正確的標識符n); return -1; int findnumber(char str,int pos) if (leading()=0) printf(常量位置不正確n); return -1; else lexicon+tokencount.kind=operand; lexicontokencount.in

13、fo.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(word)=-1) printf(表達式中存在不能識別的符號n); return -1; else if (l

14、eading()=1) if (kind(h)=rightparen) printf(不應為右括號n); return -1; else if (kind(h)!=binaryop) puttoken(h); else if (strcmp(word,+)=0); else if (strcmp(word,-)=0) puttoken(hashtablehash(); else printf( 二元運算符不正確n); return -1; else if (kind(h)=binaryop | kind(h)=rightparen) puttoken(h); else printf(二元運算符

15、不正確n); return -1; if (k=kind(h)=leftparen) parencount+; else if (k=rightparen) if (-parencount-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)-1) h=stto

16、p;top-; puttoken1(h); break; while (type!=endexpr); puttoken1(0); int process(char *instring) int len,pos; inlength=-1; parencount=0; tokencount=lastoperand; len=strlen(instring); instringlen=0; for (pos=0;poslen;) if (instringpos= ) pos+; else if (isalpha(instringpos) pos=finderror(instring,pos); e

17、lse if (isdigit(instringpos) | instringpos=.) 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( 后綴表達式:n); for (i=0;i除零錯誤n); break; case 16: if (y!=(value_type)0) return(fmod(x,

18、y); else printf( 除零錯誤n); break; case 17: return(pow(x,y); default: printf( %d是無效的二元運算符n,h); break; value_type dounary(int h,value_type x) switch(h) case 3: return(-x); case 4:return(abs(x); case 5: if (x=0) return(sqrt(x); else printf( 負數不能開平方n); break; case 6: return(exp(x); case 7: if (x0) return(

19、log(x); else printf( 負數不能求lnn); break; case 8: if (x0) return(log10(x); elseprintf( 負數不能求log10n); break; case 9: return(sin(x); case 10: return(cos(x); case 11: return(tanh(x); value_type getvalue(int h) if (kind(h)!=operand) printf( 不是一個操作數n); else return(.val);value_type evaluatepostf

20、ix() kind_type type; int h; value_type x,y; double stmaxstack; int top=-1; postlength=-1; do gettoken1(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

21、,y);break; case endexpr: x=sttop;top-; if (top-1) printf( 不正確的表達式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);fseek(fp,0,seek_end);nlen=ftell(fp);rewind(fp);pchbuf=(char*)malloc(sizeof(char)*nlen+1);if(!pchbuf)perror(內存不夠!n);exit(0);nlen=fread(pchbuf,sizeof(char),nlen,fp);fclose(fp);pchbufnlen=0;printf(從文本讀出的字符串：n);printf(%sn,pchbuf);strcpy(instring,pchbuf);printf(表達式：%s轉換為后綴表達式n,instring); while (strlen(instring)!=0) i