算法與數(shù)據(jù)結(jié)構設計

算法與數(shù)據(jù)結(jié)構設計報告（2023/2023學年第二學期）題目：算術表達式的求解專業(yè)學生姓名班級學號指導教師指導單位日期年月日評分細則評分項優(yōu)秀良好中等差遵守機房規(guī)章制度上機時的表現(xiàn)學習態(tài)度程序準備情況程序設計能力團隊合作精神課題功能實現(xiàn)情況算法設計合理性用戶界面設計報告書寫認真程度內(nèi)容詳實程度文字表達熟練程度回答問題準確度簡短評語教師簽名：年月日評分等級備注評分等級有五種：優(yōu)秀、良好、中等、及格、不及格一、課題名稱算術表達式的求解二、課題內(nèi)容和要求設計要求：給定一個算術表達式，通過程序求出最后的結(jié)果。（1）從鍵盤輸入要求解的算術表達式；（2）采用棧結(jié)構進行算術表達式的求解過程；（3）能夠判斷算術表達式正確與否；（4）對于錯誤表達式給出提示；（5）對于正確的表達式給出最后的結(jié)果。三、需求分析首先通過鍵盤輸入表達式并將字符串入棧,然后按從左到右的循環(huán)判斷表達式的格式正確與否，當表達式的+，-，×，/,?，()等運算符號間有兩個小數(shù)點時，表達式為錯誤，給出錯誤提示并轉(zhuǎn)到起始環(huán)節(jié)，然后根據(jù)給定運算順序來做運算，有括號要先算括號里面的，計算的結(jié)果賦值到浮點型數(shù)據(jù)并輸出結(jié)果。四、概要設計在此說明每個部分的算法設計說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構設計說明（如果指定存儲結(jié)構請寫出該存儲結(jié)構的定義，如果用面向?qū)ο蟮姆椒?，應該給出類中成員變量和成員函數(shù)原型聲明）。1.棧的建立先建立兩個不同的棧分別存放運算符號和數(shù)字，然后初始化棧。當從鍵盤輸入符號時，首先判斷輸入的是否是括號，若是，則在括號標志位置1，再判斷是否是負號，若為負，則再輸入一位，并將負號標志位置1；輸入字符不滿足要求時，提示錯誤，重新輸入；（1）、定義棧的抽象數(shù)據(jù)類型定義：ADTStack{

數(shù)據(jù)對象：D={ai|ai∈DateType,i=1,2,……，n，n>=0}數(shù)據(jù)關系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}基本操作：InitStack(&S)（2）、棧類型思想：本程序中棧采用的鏈式存儲結(jié)構，因為存放操作符和操作數(shù)的結(jié)點類型不一樣，所以設計了兩個結(jié)點。棧的基本操作采用了重載的方法，使兩種結(jié)點類型都能使用。（1）、存放操作符的結(jié)點：structnode2{chardata2;//存放操作符node2*next2;};（2）、存放操作數(shù)的結(jié)點：structnode{doubledata;//存放操作數(shù)node*next;};2.數(shù)字輸入當字符是數(shù)字時，若緊接該字符之后的仍然是數(shù)字，則說明輸入的為多位數(shù)，按十進制算法*10相加得到實數(shù)a入棧。3.符號輸入輸入符號時，根據(jù)不同的標志位，有不同的處理方法：若兩運算符相連，提示錯誤，重新輸入；當有左括號時，根據(jù)標志位判斷，若未找到右括號，則提示輸入錯誤，重新輸入。4.運算符號棧中運算符號op出棧，數(shù)字棧中的數(shù)字出棧并賦值給a，b，根據(jù)給定的運算優(yōu)先級（括號，*，/,+，-，?），在除數(shù)b不為0的條件下，調(diào)用Execute(floata,charop,floatb)函數(shù)，得出結(jié)果v，壓入棧中，若之前有負號（負號標志位位為1），則求其相反數(shù)v=-v，并將結(jié)果壓入數(shù)字棧中，然后不斷循環(huán)，直到遇到“=”停止，然后從數(shù)字棧輸出結(jié)果。5、本程序包含的三個模塊（1）、主程序模塊；(2)、棧模塊——實現(xiàn)棧抽象數(shù)據(jù)類型；（3）、表達式求解模塊——求解表達式值的抽象數(shù)據(jù)類型；主程序模塊表達式求解模塊棧模塊三個模塊之間的調(diào)用關系如上圖所示。6、函數(shù)的調(diào)用關系圖：主程序s.Output()s.Put()s.Help()退出程序五、詳細設計各個算法實現(xiàn)的源程序（可以是一組源程序，每個功能模塊采用不同的函數(shù)實現(xiàn)），源程序要按照寫程序的規(guī)則來編寫。要結(jié)構清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。源程序代碼：#include<iostream>usingnamespacestd;#defineStack_Size1000#defineStack_Float1000#defineTRUE1#defineFALSE0typedefstruct//建立數(shù)字棧{floatelem[Stack_Float];inttop;}Stack_float;voidInitStack(Stack_float*S)//初始化棧{S->top=-1;}intPush(Stack_float*S,floate)//進棧{if(S->top==Stack_Float-1)return(FALSE);else{S->top++;S->elem[S->top]=e;return(TRUE);}}intPop(Stack_float*S,float*x)//出棧{if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];S->top--;return(TRUE);}}intGetTop(Stack_float*S,float*x)//取棧頂{if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];return(TRUE);}}floatGetTop(Stack_floatS){floatx;GetTop(&S,&x);returnx;}voidClearStack(Stack_float*S)//清空棧{if(S->top!=-1)S->top=-1;}typedefstruct//建立字符棧{charelem[Stack_Size];//存儲定義inttop;}Stack_char;voidInitStack(Stack_char*S){S->top=-1;}intPush(Stack_char*S,charx){if(S->top==Stack_Size-1)return(FALSE);S->top++;S->elem[S->top]=x;return(TRUE);}intPop(Stack_char*S,char*x){if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];S->top--;return(TRUE);}}intGetTop(Stack_char*S,char*x){if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];return(TRUE);}}charGetTop(Stack_charS){charx;GetTop(&S,&x);returnx;}voidClearStack(Stack_char*S){if(S->top!=-1)S->top=-1;}chara[8]={'+','-','*','/','(',')','=','^'};//輸入的七種字符charp[8][8]={'>','>','<','<','<','>','>','<','>','>','<','<','<','>','>','<','>','>','>','>','<','>','>','<','>','>','>','>','<','>','>','<','<','<','<','<','<','=','','<','>','>','>','>','','>','>','>','<','<','<','<','<','','=','<', '>','>','>','>','<','>','>','>'}; //運算符之間優(yōu)先權的比較boolIns(charch)//判斷輸入的數(shù)字字符{if(ch>=48&&ch<=57)return(TRUE);elsereturn(FALSE);}boolInc(charch)//判斷輸入的運算符{if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^'||ch=='('||ch==')'||ch=='=')return(TRUE);elsereturn(FALSE);}floatGetNumber(char*ch)//數(shù)碼轉(zhuǎn)換{return(*ch-48);}doublepower(doublea,doubleb){ doubles=1.0; for(inti=0;i<b;i++) s=s*a; returns;}floatExecute(floata,charop,floatb)//運算關系的實行{switch(op){case'+':return(a+b);break;case'-':return(a-b);break;case'*':return(a*b);break;case'/':return(a/b);break; case'^':returnpower(a,b);break;default:cout<<"不能運算";break;} return0;}charCompare(charx,charch)//字符之間優(yōu)先權比較{inti,j,k;for(i=0;i<8;i++){if(x==a[i])j=i;if(ch==a[i])k=i;}returnp[j][k];}Stack_charTA;//定義字符對象Stack_floatTB;//定義數(shù)字對象floatCaculator(){ intc;InitStack(&TA);InitStack(&TB);Push(&TA,'='); cout<<endl;cout<<"請輸入一個表達式串（以=結(jié)束）"<<endl; cout<<"-----------------------------------"<<endl;charch;intw=0,q=0,y=0,z=0,m=0;//w=0表示無負號輸入，q=0表示無數(shù)字輸入，y=0表示有字符輸入，z=0表示無括號輸入，m=0表示無負括號標記 floatn=0,v,a,b; charop;ch=getchar();if(!Ins(ch)){if(ch=='(')z=1;elseif(ch=='-'){w=1;ch=getchar();}//記錄輸入負號else{ cout<<endl;cout<<"您輸入的表達式有誤【(1)表達式不能以運算符（除取反外）開頭】，請重新輸入!"<<endl; cout<<"---------------------------------------"<<endl;fflush(stdin);//清理緩存ClearStack(&TA);Caculator();exit(1);}}while(ch!='='||GetTop(TA)!='='){if(Ins(ch)){n=n*10+GetNumber(&ch);q=1;//記錄輸入數(shù)字y=0;//記錄輸入字符ch=getchar();}if(Inc(ch)){if(ch=='(')z=1;if(w==1){if(q==0){if(z==1){Push(&TA,ch);z=0;m=2;//記錄負的左括號ch=getchar();continue;}elseif(ch=='-'){w=0;ch=getchar();}/*else{ cout<<endl;cout<<"您輸入的表達式有誤【(2)表達式中有不符合要求的運算】，請重新輸入!"<<endl; cout<<"--------------------------------------"<<endl;fflush(stdin);ClearStack(&TA);Caculator();exit(1);}*/}else{cout<<"w"<<w<<endl;n=-n;w=0; if(m==2){n=-n;m--;cout<<"m"<<m<<endl;}}//表達式中有負號和括號時的運算}if(q==1){Push(&TB,n);n=0;q=0;}if(y==1){if(GetTop(TA)=='('&&ch=='-'){w=1;ch=getchar();}elseif(ch=='(')z=1;else{ cout<<endl;cout<<"您輸入的表達式有誤【(2)表達式中有運算符位置錯誤】，請重新輸入!"<<endl; cout<<"---------------------------------------"<<endl;fflush(stdin);ClearStack(&TA);ClearStack(&TB);Caculator();exit(1);}}if(y==0||z==1){switch(Compare(GetTop(TA),ch)){case'<':Push(&TA,ch);//目前輸入運算符的優(yōu)先級大于字符棧頂運算符優(yōu)先級，將此運算符進棧y=1;z=0;ch=getchar();break;case'>':Pop(&TA,&op);//目前輸入運算符的優(yōu)先級小于字符棧頂運算符//優(yōu)先級，將棧頂運算符出棧Pop(&TB,&b);//并且將數(shù)字棧的a,b出棧進行運算Pop(&TB,&a);if(op=='/'&&b==0){ cout<<endl;cout<<"您輸入的表達式有誤（分子不能為0），請重新輸入!"<<endl; cout<<"---------------------------------------"<<endl;fflush(stdin);ClearStack(&TA);ClearStack(&TB);Caculator();exit(1);}v=Execute(a,op,b);if(m==1){v=-v;m=0;}Push(&TB,v);//將運算結(jié)果壓進數(shù)字棧break;case'=':Pop(&TA,&op);ch=getchar();break;case'$': cout<<endl;cout<<"括號不匹配，請重新輸入!"<<endl; cout<<"------------------------------------"<<endl;fflush(stdin);ClearStack(&TA);ClearStack(&TB);Caculator();exit(1);}}}if(!Inc(ch)&&!Ins(ch)){ cout<<endl;cout<<"您輸入的表達式有誤（不能出現(xiàn)非法字符），請重新輸入!"<<endl; cout<<"----------------------------------------"<<endl;fflush(stdin);ClearStack(&TA);ClearStack(&TB);Caculator();exit(1);}}v=GetTop(TB); cout<<"--------------------------------------------"<<endl; cout<<"計算結(jié)果為："<<endl;cout<<v<<endl; cout<<"--------------------------------------------"<<endl; system("pause"); cout<<"--------------------------------------------"<<endl; cout<<"請選擇:"<<endl; cout<<"1.進入系統(tǒng)"<<endl; cout<<"2.退出系統(tǒng)"<<endl; cout<<"---------------------------------------------"<<endl; cin>>c; switch(c) { case1:fflush(stdin); ClearStack(&TA);ClearStack(&TB); Caculator();break; case2:return0; default:cout<<"error"<<endl;break; } return0;}intmain(){ intc; cout<<"--------------------------------------------------------"<<endl; cout<<endl; cout<<"-------------歡迎使用算術表達式求解系統(tǒng)!----------------"<<endl; cout<<endl; cout<<"-----------------------------------------"<<endl; cout<<"1.進入系統(tǒng)"<<endl; cout<<"2.退出系統(tǒng)"<<endl; cout<<"-----------------------------------------"<<endl; cin>>c; switch(c) { case1:fflush(stdin); ClearStack(&TA);ClearStack(&TB); Ca