C語言_算數(shù)表達式求值_課程設計報告.doc

目 錄一概述2二總體方案設計3三詳細設計4四程序的調(diào)試與運行結(jié)果說明5五課程設計總結(jié)6參考文獻7附錄.8 一 概述一、課程設計的目的與要求本課程設計是為了配合數(shù)據(jù)結(jié)構(gòu)課程的開設,通過設計一個完整的程序,使學生掌握數(shù)據(jù)結(jié)構(gòu)的應用,算法的編寫,類C語言的算法轉(zhuǎn)換成C程序并用Turbo C2.0或Visual C+6.0上機調(diào)試的基本方法。要求如下: 1.要充分認識課程設計對自己的重要性,認真做好課程設計前的各項準備工作。 2.既要虛心接受老師的指導,又要充分發(fā)揮主觀能動性.結(jié)合課題,獨立思考,努力鉆研,勤于實踐,勇于創(chuàng)新。 3.獨立按時完成規(guī)定的工作任務,不得弄虛作假,不準抄襲他人內(nèi)容,否則成績以不及格計。 4.課程設計期間,無故缺席按曠課處理;缺席時間達四分之一以上者,其成績按不及格處理。 5.在設計過程中,要嚴格要求自己,樹立嚴肅,嚴密,嚴謹?shù)目茖W態(tài)度,必須按時,按質(zhì),按量完成課程設計。 6.小組成員之間,分工明確,但要保持聯(lián)系暢通,密切合作,培養(yǎng)良好的互相幫助和團隊協(xié)作精神。二、需求分析本課程設計的課題為表達式求值，要求：1.用戶將表達式原樣輸入（在表達式結(jié)尾加上#），能得出結(jié)果（為減小難度，運算結(jié)果的10進制形式的值，不超過longdouble的存儲范圍）；2.輸入的數(shù)可以為小數(shù)（為減小難度，小數(shù)的整數(shù)與小數(shù)部分均不超過10位），負數(shù)（如果負數(shù)前有運算符，則應將負數(shù)括起來），以及2進制，8進制，10進制，16進制的數(shù)（為減小難度，數(shù)出的結(jié)果都以10進制形式表示）；3.運算符號包括（）、+、*、/；括號可以多重；二 總體方案設計1.使用雙鏈表的數(shù)據(jù)結(jié)構(gòu)表示數(shù)據(jù)的存儲，將用戶輸入的表達式以字符形式存入雙鏈表中。2.對以負數(shù)開頭、以括號開頭、左括號后緊跟負數(shù)的特殊情況作處理。3.將數(shù)與運算符分開；4.依次找到表達式最內(nèi)層括號，次內(nèi)層括號.每次找到括號內(nèi)的表達式，便將其進行只有 加減乘除運算的計算。結(jié)構(gòu)體類型：/用來存儲字符的結(jié)點類型typedef struct CharNodechar c;struct CharNode *next;CharNode;/用來存儲數(shù)的結(jié)點類型typedef struct IntNodelong double i;struct IntNode *next;IntNode;/用來存儲數(shù)的結(jié)點類型typedef struct Nodelong double n;struct Node_ys_char *next;Node;/用來存儲運算符的結(jié)點類型typedef struct Node_ys_charchar c;struct Node_ys_char *next_c;struct Node *next;Node_ys_char;三 詳細設計我任務是整個程序的算法設計，以及部分子函數(shù)的編寫，經(jīng)過其他組員編寫的子函數(shù)的處理，將表達式變?yōu)橐粋€普通的表達式，其中數(shù)與運算符已經(jīng)分開，將這個表達式的頭指針傳遞到我所編寫函數(shù)中，運算思想為：找到最內(nèi)層的一對括號，計算括號間的表達式的值，得到值之后，用這個值替換掉原始位置上的一對括號，以及其中的表達式。例如（6.5-2*2.25）*2-6）/2+1.5）+3#，第一次替換后為（2*2-6）/2+1.5）+3#，第二次替換后為（-2/2+1.5）+3#，第三次替換后為0.5+3#，當沒有括號時調(diào)用四則運算函數(shù)直接計算。如果一開始輸入的表達式中沒有括號，則直接調(diào)用四則運算函數(shù)進行計算。整個程序的算法思想見流程圖。函數(shù)的功能如下：char Precede(char x,char y) 運算符優(yōu)先級判斷CharNode *CreatRegister()輸入表達式，并對特殊情況做處理Node *StackChange(CharNode *top,int m)將數(shù)與運算符分開，并將其他進制轉(zhuǎn)化為10進制Node *Compute(Node *p)作只有加減乘除運算的表達式求值Node *GetOutcome(Node *head)求用戶輸入表達式的值main（）主函數(shù)主要部分的詳細流程圖）開始輸入表達式特殊情況處理將數(shù)與運算符分開找到最內(nèi)層一堆括號將括號內(nèi)表達式用指針帶出將括號內(nèi)表達式用指針帶出進行只有加減乘除運算表達式求值用表達式值替換掉括號及括號間表達式取當前表達式首指針進行只有加減乘除運算表達式求值得出結(jié)果否是循環(huán)四 程序的調(diào)試與運行結(jié)果說明在編寫只有加減乘除的表達式求值的表達式求值時，原始思想是用兩個指針分別指向相鄰的兩個運算符，若后者大，則進行后面運算符的運算，然后指針繼續(xù)后移，當再次遇到的兩個運算符，前者與后者相等，則進行前面運算符的運算；此算法思想錯誤，導致計算6+2*3+1#結(jié)果正確，而當計算6-2*3+1#時，卻得出-1的錯誤結(jié)果，正確結(jié)果為+1；這是因為先計算2*3得到6；表達式變?yōu)?-6+1#；接著進行6+1的運算，得到7；當前計算循序錯誤，導致結(jié)果錯誤。后來將程序改為先進行優(yōu)先級高的運算符的運算，當優(yōu)先級相等時，不計算。指針后移，當遇到表達式結(jié)束標志時，便將指針移到表達式的頭位置，此時，判斷是否進行運算的條件發(fā)生變化，當前后運算符的優(yōu)先級相等時，進行前面運算符的運算；使得第一次將乘除運算符運算完，第二進行只有加減運算符的運算五 課程設計總結(jié)進過調(diào)試程序能得出大多數(shù)表達式的正確結(jié)果，雖然經(jīng)過了一些特殊情況表達式的輸入，得出了正確結(jié)果，但不排除還有某些漏洞使得一些特殊情況的表達式不能得出正確結(jié)果，還有待進一步的測試。特點：本程序能進行小數(shù)、以及2進制、8進制、16進制的運算。不足：結(jié)果都以10進制形式表示，用戶不能改變；結(jié)果的10進制形式不能超出longdouble型數(shù)據(jù)能存儲的數(shù)的范圍；進一步的設想：將數(shù)分段存儲，內(nèi)存動態(tài)分配，使其能進行天文數(shù)字運算；錄入其他的運算符例如指數(shù)運算，開方運算，取余運算，解一元一次方程，解二元一次方程組。附錄：源代碼：/用來存儲字符的結(jié)點類型typedef struct CharNodechar c;struct CharNode *next;CharNode;/用來存儲數(shù)的結(jié)點類型typedef struct IntNodelong double i;struct IntNode *next;IntNode;/用來存儲數(shù)的結(jié)點類型typedef struct Nodelong double n;struct Node_ys_char *next;Node;/用來存儲運算符的結(jié)點類型typedef struct Node_ys_charchar c;struct Node_ys_char *next_c;struct Node *next;Node_ys_char;char Precede(char x,char y)/運算符優(yōu)先級判斷 int i,j;int from55=0,0,-1,-1,0,0,0,-1,-1,0,1,1,0,0,1,1,1,0,0,1,0,0,-1,-1,0;/定義一個二維數(shù)組存放算術符號的優(yōu)先級 switch(x)case +:i=0;break;case -:i=1;break;case *:i=2;break;case /:i=3;break;case #:i=4;break;switch(y)case +:j=0;break;case -:j=1;break;case *:j=2;break;case /:j=3;break;case #:j=4;break;if(fromij=1)/說明運算符i的優(yōu)先級比j的優(yōu)先級高return ;if(fromij=-1)return c);scanf(%c,&p-c);if(q-c=-)p=(CharNode *)malloc(sizeof(CharNode);p-c=0;p-next=q;top=p;p=q;if(q-c=()e=(CharNode *)malloc(sizeof(CharNode);e-c=0;p=(CharNode *)malloc(sizeof(CharNode);p-c=+;e-next=p;p-next=q;p=q;top=e;while(p-c!=#)q=(CharNode *)malloc(sizeof(CharNode);scanf(%c,&q-c);if(p-c=()&(q-c=-)e=(CharNode *)malloc(sizeof(CharNode);e-c=0;e-next=q;p-next=e;p=q;elsep-next=q;p=q;p-c=+;p-next=(CharNode *)malloc(sizeof(CharNode);p-next-c=0;p=p-next;p-next=(CharNode *)malloc(sizeof(CharNode);p-next-c=#;return top;/將數(shù)與運算符分開，并將其他進制轉(zhuǎn)化為10進制Node *StackChange(CharNode *top,int m)CharNode *p,*q;long double x=0,y=0;char a10,b10;int n=0,i=0,JiWei,max,min=47,mark_1=0,mark_2=0,h,k=0;Node *node,*head;Node_ys_char *node_char;switch(m)case 2:JiWei=2;max=50;break;case 8:JiWei=8;max=56;break;case 10:JiWei=10;max=97;break;case 16:JiWei=16;max=103;break;p=q=top;while(p-c !=#)while(q-cmin)&(q-cc=46)if(q-c=46)mark_1=1;q=q-next;if(mark_1=0)an=q-c;q=q-next;n+;if(mark_1=1)bi=q-c;q=q-next;i+;for(h=n-1;h=0;h-)x=(an-h-1-48)*pow(JiWei,h)+x;/for(h=0;hn=x+y;mark_1=0;n=0;i=0;if(mark_2=1)node_char-next=node;node_char=(Node_ys_char *)malloc(sizeof(Node_ys_char);node_char-c=q-c;node-next=node_char;node_char-next_c=NULL;node_char-next=NULL;if(q-c=#)node-next=(Node_ys_char *)malloc(sizeof(Node_ys_char);node-next-c=#;return head;q=q-next;if(q-ccnext_c=(Node_ys_char*)malloc(sizeof(Node_ys_char);node_char-next_c-c=q-c;q=q-next ;/node-next=node_char;node_char=node_char-next_c;node_char-next_c=NULL;node_char-next=NULL;elsenode-next=node_char;node_char-next_c=NULL;node_char-next=NULL;p=q;n=0;x=0;y=0;if(mark_2=0)head=node;mark_2=1;return head;/作只有加減乘除運算的表達式求值Node *Compute(Node *p)int mark=0;Node *m,*n;char max_char,min_char;m=n=p;while(p-next-c!=#)max_char=n-next-c;n=n-next-next;min_char=n-next-c;if(Precede(max_char,min_char)=|mark=1)switch(m-next-c)case +:m-n =m-n + n-n ;break;case -:m-n =m-n - n-n ;break;case *:m-n =m-n * n-n ;break;case /:m-n =m-n / n-n ;break;m-next=n-next;n=m;if(m-next-c=#)m=n=p;mark=1;return m;/求用戶輸入表達式的值Node *GetOutcome(Node *head)Node *p,*q,*R;Node_ys_char *m,*n,*t,*k;n=(Node_ys_char *)malloc(sizeof(Node_ys_char);n-c=(;p=q=head;while(n-c!=)&(q-next-c!=#)if(q-next-c=()m=q-next;k=m;else if(q-next-next_c=NULL)q=q-next-next;elsem=q-next-next_c;k=q-next;/t=q-next;if(m-c=()t=k;k=m;while(m-next_c!=NULL)m=m-next_c;if(m-c=()t=k;k=m;q=m-next ;if(q-next-c=)n=q