本科畢業(yè)設(shè)計-基于c語言的表達式求解課程設(shè)計論文

摘要通過數(shù)據(jù)結(jié)構(gòu)這門課程，我們較深入的了解到了棧，棧是一種重要的線性結(jié)構(gòu)，它廣泛應(yīng)用于各種軟件系統(tǒng)中，因此在面向?qū)ο蟮某绦蛟O(shè)計中，它們是多型數(shù)據(jù)類型。本次試驗我們將探索表達式求值問題，表達式求值是程序設(shè)計語言編譯中的一個最基本的問題，它的實現(xiàn)是棧應(yīng)用的又一個典型的例子。通過實在計算機中，算術(shù)表達式由常量、變量、運算符和括號組成。由于不同的運算符具有不同的優(yōu)先級，又要考慮括號，因此，算術(shù)表達式的求值不可能嚴格地從左到右進行。因而在程序設(shè)計時，借助棧實現(xiàn)。用一個一維數(shù)組存放從鍵盤輸入的表達式,表達式中可包含：加（+）、減（-）、乘（*）、除（/）,括號（（,））等運算符。要對輸入的表達式進行檢查，看是否是合格的表達式，如遇到錯誤則終止，不進行計算；例如：括號不配對、除數(shù)不為零等；輸入的表達式可以是常量表達式，也可以是變量表達式；如果是常量表達式，則直接輸出結(jié)果；如果是變量表達式，通過對變量的不斷賦值，計算變量取不同值時表達式的結(jié)果。參與運算的操作數(shù)可以是整型，也可以是浮點型。關(guān)鍵詞：棧；先進先出；帶括號的表達式；表達式求值

目錄TOC\o"1-3"\h\u226451緒論 采用類c語言定義相關(guān)的數(shù)據(jù)類型2.1設(shè)定棧的數(shù)據(jù)類型定義ADTStack{數(shù)據(jù)對象：D={ai|ai∈DateType,i=1,2,……，n，n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S；StackEmpty(S)初始條件：棧S已存在；操作結(jié)果：若S為空棧，則返回0，否則返回1；GetTop(S,&e)初始條件：棧S已存在；操作結(jié)果：若棧S不空，則以e返回棧頂元素；Push(&S,e)初始條件：棧S已存在；操作結(jié)果：在棧S的棧頂插入新的棧頂元素e；Pop(&S,&e)初始條件：棧S存在；操作結(jié)果：刪除S的棧頂元素，并以e返回其值；DestroyStack(&S)

初始條件：棧S已存在。操作結(jié)果：銷毀棧S。

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。StackEmpty(S)

初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE；

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的數(shù)據(jù)元素個數(shù)，即棧的長度。}2.2設(shè)定表達式求值的抽象數(shù)據(jù)類型定義：classEva{public: voidGetcha(char*name);操作結(jié)果：重鍵盤獲取表達式 OperandTypeEvaluateExpression();操作結(jié)果：計算表達式的值 voidOutput();操作結(jié)果：輸出常量表達式的結(jié)果 charMenu();操作結(jié)果：主菜單選項 intcheck();操作結(jié)果：檢查表達式是否正確，若正確返回1，否則返回0； intSimple(char*p,inti);操作結(jié)果：判斷運算符-，若是減號返回1，否則返回0； OperandTypeEvaluate();操作結(jié)果：對變量表達式中的變量進行提?。淮娣旁趙ord[10]中； doublechange();操作結(jié)果：對變量表達式中的變量賦值； charMenu2();操作結(jié)果：對變量表達式中變量賦值的菜單； voidPut();操作結(jié)果：輸出變量表達式的結(jié)果； voidHelp();操作結(jié)果：調(diào)用一個.txt文檔，為用戶提供使用幫助；private: charcha[100];//存放輸入的表達式charword[10];//存放表達式中的變量 intswit(charop);操作結(jié)果：判斷運算符在優(yōu)先級表中的下標； intIn(charc);操作結(jié)果：判斷是否是運算符，若是返回1，否則返回0； charPrecede(charop,charc);操作結(jié)果：比較兩個字符的優(yōu)先級，返回<、>、或=； OperandTypeOperate(OperandTypea,charop,OperandTypeb);操作結(jié)果：計算兩個操作數(shù)的運算，返回運算的結(jié)

3各模塊的偽碼算法3.1存放操作符的模塊structnode2{ chardata2;//存放操作符 node2*next2;};定義一個名為node2的存放操作符的結(jié)點，設(shè)data的數(shù)據(jù)類型為char型，data用來存放表達式中的操作符，定義一個指針next2,使它指向data里的值。3.2存放操作數(shù)的模塊structnode{ doubledata;//存放操作數(shù) node*next;};定義一個名為node的存放操作數(shù)的結(jié)點，設(shè)data的數(shù)據(jù)類型為double型，data存放的是表達式中的操作數(shù)，定義一個名為next的指針，它指向的是data里的數(shù)值。3.3棧的基本操作設(shè)置模塊intInitStack(Linked_stack*top)//初始化，設(shè)棧為空棧（top->next=NULL）；intStackEmpty(Linked_stacktop)//若棧為空（top->next=NULL），則返回1，否則返回0；intPush(Linked_stacktop,Datetypee)//若申請動態(tài)內(nèi)存成功，則在top的棧頂插入元素e，并返回1，//否則返回0；intPop(Linked_stacktop,Datetype*e)//若棧不空，則刪除top的棧頂元素并以e帶回其值，并且返回1，//否則返回0；intGetTop(Linked_stacktop,Datetype*e)//若棧top不空，則以e帶回其值，則返回1，否則返回4函數(shù)的調(diào)用圖4.1系統(tǒng)總結(jié)構(gòu)圖主菜單主菜單退出程序輸出結(jié)果計算表達式輸入表達式退出程序輸出結(jié)果計算表達式輸入表達式 圖4.1系統(tǒng)總結(jié)構(gòu)圖4.2算法模塊的調(diào)用關(guān)系開始開始NO，出現(xiàn)錯誤提示NO，出現(xiàn)錯誤提示取棧頂元素取棧頂元素建立空棧建立空棧入棧入棧入棧入棧若s已存在插入e為新的棧頂元素若s存在并非空，用e返回s的棧頂元素若s已存在插入e為新的棧頂元素若s存在并非空，用e返回s的棧頂元素若s已存在刪除s的棧頂元素若s已存在刪除s的棧頂元素輸入表達式輸入表達式計算表達式計算表達式正確？Yes正確？Yes輸出結(jié)果輸出結(jié)果退出退出圖4.2算法關(guān)系調(diào)用圖計算表達式輸出結(jié)果結(jié)束開始優(yōu)先級比較算法operate算法存放操作字符存放操作數(shù)計算表達式輸出結(jié)果結(jié)束開始優(yōu)先級比較算法operate算法存放操作字符存放操作數(shù)Inputexpression建立棧 表達式正確表達式不正確圖4.3程序流程圖5調(diào)試及測試5.1調(diào)試分析5.1.1調(diào)試中遇到的問題及對問題的解決方法表5.1測試列表測試項目測試用例計算結(jié)果預(yù)期結(jié)果實驗結(jié)果基本測試333表達式結(jié)果為：31+2*3-4/255表達式結(jié)果為：511+223333表達式結(jié)果為：331+22*(5-3)/41212表達式結(jié)果為：122.5-3.4/2+1*22.82.8表達式結(jié)果為：2.82^2^3256256表達式結(jié)果為：2562^2.5^350535.250535.2表達式結(jié)果為：50535.2-2*3+4/2-4-4表達式結(jié)果為：-43*(-2-4)+2-16-16表達式結(jié)果為：-16X^2+xx=31212表達式結(jié)果為：12容錯測試1+2（2與（之間沒有操作符2與（之間沒有操作符錯誤提示：括號前不能直接跟操作數(shù)續(xù)表5.13/(2*3-6)+2除數(shù)為0除數(shù)為0錯誤提示：除數(shù)不能為零2+3)(-5括號不匹配括號不匹配錯誤提示：括號不匹配！1+++1出現(xiàn)3個+出現(xiàn)3個+錯誤提示：操作符不能連續(xù)出現(xiàn)！222與2之間無操作符2與2之間無操作符錯誤提示：操作符間應(yīng)運操作符!1#1#是非法字符#是非法字符錯誤提示：表達式中含有非法字符！3(2+5)3與（之間沒有操作符3與（之間沒有操作符錯誤提示：括號前不能直接跟操作數(shù)！5.1.2算法的時間復(fù)雜度和空間復(fù)雜度時間和空間性能分析：時間上，對于含n個字符的表達式，無論是對其進行合法性操作還是進行入棧出棧操作n次，其時間復(fù)雜度為O(n),空間上由于用數(shù)組來存儲輸入的表達式，用棧來存儲運算中的數(shù)據(jù)和運算符，而棧的本質(zhì)也用到數(shù)組，數(shù)組在定義時必須確定大小，在不知表達式的情況下確定數(shù)組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。表5.2算法的時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度空間復(fù)雜度5.2測試結(jié)果在設(shè)計程序的過程中，出現(xiàn)程序不能運行，發(fā)現(xiàn)不能找到表達式結(jié)束的標識符，因此，在設(shè)計的時候需要認為動態(tài)的添加結(jié)束標識符‘#’，是程序能夠順利的運行。在程序無誤運行之后屏幕出現(xiàn)對話窗口提示，在數(shù)字提示下進行輸入表達式，檢查表達式，計算表達式，輸出結(jié)果。圖5.2表達式1+2(運行結(jié)果圖圖5.2表達式2/0運行結(jié)果圖圖5.2表達式1++1運行結(jié)果圖圖5.2表達式3運行結(jié)果圖圖5.2表達式1=2*3-4/2運行結(jié)果圖圖5.2表達式11+22運行結(jié)果圖圖5.2表達式1+22（5-3）/4運行結(jié)果圖6源程序#include<stdio.h>#include<string.h>#include<conio.h>//函數(shù)結(jié)果狀態(tài)代碼#definePLUS0#defineMINUS1#definePOWER2#defineDIVIDE3#defineLEFTP4#defineRIGHP5#defineSTARTEND6#defineDIGIT7#definePOINT8#defineNUM7#defineNO32767#defineSTACKSIZE20//存儲空間初始分配量chara[]={'+','-','*','/','(',')','#'};intPriorityTable[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1},{1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0,NO},{1,1,1,1,NO,1,1},{-1,-1,-1,-1,-1,NO,0}};intmenu(void);//定義一個整型的菜單voidInputExpression(charstr[])//構(gòu)造輸入表達式{intlen;//長度printf("Inputexpressionstring:\n");scanf("%s",str);len=strlen(str);str[len]='#';str[len+1]='\0';}intGetCharType(charch){inti;for(i=0;i<NUM;i++)if(ch==a[i])return(i);//若字符與數(shù)組a[i]值相等，則輸入i的值if(ch>='0'&&ch<='9')return(DIGIT);if(ch=='.')return(POINT);//若輸入字符“.”則返回POINTreturn(-1);}doubleOperate(doublea,inttheta,doubleb)//定義一個操作類，給定雙精度型變量a,b和一個整型{doublex;switch(theta){case0:x=a+b;//當為0時，輸出表達式x=a+b結(jié)束程序break;case1:x=a-b;break;case2:x=a*b;break;case3:x=a/b;break;}return(x);}intEXCUTE(char*str,double*Result)//定義一個char類型的指針str和一個double類型的指針Result{intpp,strlength,topTr,topNd,CharType,OPTR[STACKSIZE];//定義int型變量，和壓入操作符的棧長度doublenumber,temp,OPND[STACKSIZE];//定義double型變量和壓入操作數(shù)的棧長度OPTR[0]=STARTEND;topTr=1;topNd=0;pp=0;while((str[pp])){CharType=GetCharType(str[pp]);switch(CharType){case-1:return(0);caseDIGIT:number=0;while(str[pp]>='0'&&str[pp]<='9'){number=number*10+(str[pp]-48);pp++;}if(str[pp]=='.'){temp=10.0;pp++;while(str[pp]>='0'&&str[pp]<='9'){number=number+(str[pp]-48)/temp;temp=temp*10;pp++;}}OPND[topNd]=number;//壓入操作數(shù)的棧topNd++;break;casePOINT:number=0;temp=10.0;pp++;while(str[pp]>='0'&&str[pp]<='9'){number=number+(str[pp]-48)/temp;temp=temp*10;pp++;}OPND[topNd]=number;topNd++;break;casePLUS:caseMINUS:casePOWER:caseDIVIDE:if(PriorityTable[OPTR[topTr-1]][CharType]==-1){OPTR[topTr]=CharType;//壓入操作符的棧topTr++;pp++;}else{OPND[topNd-2]=Operate(OPND[topNd-2],OPTR[topTr-1],OPND[topNd-1]);topNd--;topTr--;}break;caseLEFTP:OPTR[topTr]=CharType;topTr++;pp++;break;caseRIGHP:while(OPTR[topTr-1]!=LEFTP){if(OPTR[topTr-1]==STARTEND)return(0);//如果操作數(shù)的棧是最末尾一個，則輸出0if(PriorityTable[OPTR[topTr-1]][CharType]==1){OPND[topNd-2]=Operate(OPND[topNd-2],OPTR[topTr-1],OPND[topNd-1]);topNd--;topTr--;}elsebreak;}topTr--;pp++;break;caseSTARTEND:while(OPTR[topTr-1]!=STARTEND){OPND[topNd-2]=Operate(OPND[topNd-2],OPTR[topTr-1],OPND[topNd-1]);topNd--;topTr--;}if(topNd==1){*Result=OPND[0];return(1);}elsereturn(0);}}return(1);}intmain(){intnum,flag;doubleresult;charstr[256];str[0]='0';while(1){num=menu();switch(num){case1:InputExpression(str);flag=0;printf("%s\n",str);getchar();break;case2:if(str[0]=='0'){printf("ExpressionisEmpty!");getchar();break;}if(!EXCUTE(str,&result))//如果表達式錯我誤{printf("Theexpressionhaserror!\n");getchar();}else{printf("calulationhasfinished!\n");getchar();flag=1;}break;case3:if(flag){printf("#%s=%lf\n",str,result);getchar();}break;case4:break;}if(num==4)break;}}intmenu(void){intnum;printf("%20c1--inputexpression\n",'');//菜單欄顯示出輸入表達式printf("%20c2--calculationexpression\n",'');//菜單欄顯示出計算表達式printf("%20c3--printresult\n",'');//菜單欄顯示出輸出結(jié)果printf("%20c4--Quit\n",'');//菜單欄顯示出結(jié)束printf("pleaseselect1,2,3,4:");do{scanf("%d",&num);}while(num<1||num>4);return(num);}

7設(shè)計總結(jié)這次的課程設(shè)計讓我感受頗多，我就覺得我們的這一個課題應(yīng)該是一個還不錯的題目，因為上課的時候我認真聽了，也就是說我應(yīng)該可以做好，而且像這樣的問題在網(wǎng)絡(luò)上可以找到很多相關(guān)的內(nèi)容。但是在我們真正開始做的時候我卻發(fā)現(xiàn)問題不是我想像的那么簡單，我們遇到了很多的麻煩。首先，在我們開始做的時候發(fā)現(xiàn)根本不知道該從什么地方下手，接著我們便開始上網(wǎng)查找，但是網(wǎng)絡(luò)上的東西很多都是沒有用的，于是自己開始去圖書館找資料，看了很有關(guān)棧方面的知識以后，開始對棧與隊列有了一定的了解，于是在掌握了這些基礎(chǔ)知識之上，我就對我們的課題進行分析。其次，我們發(fā)現(xiàn)我遇到了不少問題，但是當我們遇到不懂的問題，我就和組員一起討論，逐步將程序的一個個功能實現(xiàn)。雖然設(shè)計的過程是比較辛苦的，但是當我們看到設(shè)計成功的時候我們非常的開心。畢竟這一設(shè)計是我們親手完成的。畢竟我們從這次的課程設(shè)計中學到了很多知識。例如：棧與隊列的算法，我們是經(jīng)過了認真的復(fù)習，才基本掌握了。還有，我們還復(fù)習了C語言的相關(guān)知識，因為我們感覺到在編程序的時候，我們明顯感覺到自己的C語言，以及數(shù)據(jù)結(jié)構(gòu)方面的知識還是有所欠缺的。例如：我們的課程設(shè)計用到了文件有關(guān)方面的知