算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告（2023/2023學(xué)年第二學(xué)期）題目：算術(shù)表達(dá)式的求解專業(yè)學(xué)生姓名班級學(xué)號指導(dǎo)教師指導(dǎo)單位日期年月日評分細(xì)則評分項(xiàng)優(yōu)秀良好中等差遵守機(jī)房規(guī)章制度上機(jī)時(shí)的表現(xiàn)學(xué)習(xí)態(tài)度程序準(zhǔn)備情況程序設(shè)計(jì)能力團(tuán)隊(duì)合作精神課題功能實(shí)現(xiàn)情況算法設(shè)計(jì)合理性用戶界面設(shè)計(jì)報(bào)告書寫認(rèn)真程度內(nèi)容詳實(shí)程度文字表達(dá)熟練程度回答問題準(zhǔn)確度簡短評語教師簽名：年月日評分等級備注評分等級有五種：優(yōu)秀、良好、中等、及格、不及格一、課題名稱算術(shù)表達(dá)式的求解二、課題內(nèi)容和要求設(shè)計(jì)要求：給定一個(gè)算術(shù)表達(dá)式，通過程序求出最后的結(jié)果。（1）從鍵盤輸入要求解的算術(shù)表達(dá)式；（2）采用棧結(jié)構(gòu)進(jìn)行算術(shù)表達(dá)式的求解過程；（3）能夠判斷算術(shù)表達(dá)式正確與否；（4）對于錯(cuò)誤表達(dá)式給出提示；（5）對于正確的表達(dá)式給出最后的結(jié)果。三、需求分析首先通過鍵盤輸入表達(dá)式并將字符串入棧,然后按從左到右的循環(huán)判斷表達(dá)式的格式正確與否，當(dāng)表達(dá)式的+，-，×，/,?，()等運(yùn)算符號間有兩個(gè)小數(shù)點(diǎn)時(shí)，表達(dá)式為錯(cuò)誤，給出錯(cuò)誤提示并轉(zhuǎn)到起始環(huán)節(jié)，然后根據(jù)給定運(yùn)算順序來做運(yùn)算，有括號要先算括號里面的，計(jì)算的結(jié)果賦值到浮點(diǎn)型數(shù)據(jù)并輸出結(jié)果。四、概要設(shè)計(jì)在此說明每個(gè)部分的算法設(shè)計(jì)說明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義，如果用面向?qū)ο蟮姆椒?，?yīng)該給出類中成員變量和成員函數(shù)原型聲明）。1.棧的建立先建立兩個(gè)不同的棧分別存放運(yùn)算符號和數(shù)字，然后初始化棧。當(dāng)從鍵盤輸入符號時(shí)，首先判斷輸入的是否是括號，若是，則在括號標(biāo)志位置1，再判斷是否是負(fù)號，若為負(fù)，則再輸入一位，并將負(fù)號標(biāo)志位置1；輸入字符不滿足要求時(shí)，提示錯(cuò)誤，重新輸入；（1）、定義棧的抽象數(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)（2）、棧類型思想：本程序中棧采用的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因?yàn)榇娣挪僮鞣筒僮鲾?shù)的結(jié)點(diǎn)類型不一樣，所以設(shè)計(jì)了兩個(gè)結(jié)點(diǎn)。棧的基本操作采用了重載的方法，使兩種結(jié)點(diǎn)類型都能使用。（1）、存放操作符的結(jié)點(diǎn)：structnode2{chardata2;//存放操作符node2*next2;};（2）、存放操作數(shù)的結(jié)點(diǎn)：structnode{doubledata;//存放操作數(shù)node*next;};2.數(shù)字輸入當(dāng)字符是數(shù)字時(shí)，若緊接該字符之后的仍然是數(shù)字，則說明輸入的為多位數(shù)，按十進(jìn)制算法*10相加得到實(shí)數(shù)a入棧。3.符號輸入輸入符號時(shí)，根據(jù)不同的標(biāo)志位，有不同的處理方法：若兩運(yùn)算符相連，提示錯(cuò)誤，重新輸入；當(dāng)有左括號時(shí)，根據(jù)標(biāo)志位判斷，若未找到右括號，則提示輸入錯(cuò)誤，重新輸入。4.運(yùn)算符號棧中運(yùn)算符號op出棧，數(shù)字棧中的數(shù)字出棧并賦值給a，b，根據(jù)給定的運(yùn)算優(yōu)先級（括號，*，/,+，-，?），在除數(shù)b不為0的條件下，調(diào)用Execute(floata,charop,floatb)函數(shù)，得出結(jié)果v，壓入棧中，若之前有負(fù)號（負(fù)號標(biāo)志位位為1），則求其相反數(shù)v=-v，并將結(jié)果壓入數(shù)字棧中，然后不斷循環(huán)，直到遇到“=”停止，然后從數(shù)字棧輸出結(jié)果。5、本程序包含的三個(gè)模塊（1）、主程序模塊；(2)、棧模塊——實(shí)現(xiàn)棧抽象數(shù)據(jù)類型；（3）、表達(dá)式求解模塊——求解表達(dá)式值的抽象數(shù)據(jù)類型；主程序模塊表達(dá)式求解模塊棧模塊三個(gè)模塊之間的調(diào)用關(guān)系如上圖所示。6、函數(shù)的調(diào)用關(guān)系圖：主程序s.Output()s.Put()s.Help()退出程序五、詳細(xì)設(shè)計(jì)各個(gè)算法實(shí)現(xiàn)的源程序（可以是一組源程序，每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)），源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。源程序代碼：#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)//進(jìn)棧{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ùn)算符之間優(yōu)先權(quán)的比較boolIns(charch)//判斷輸入的數(shù)字字符{if(ch>=48&&ch<=57)return(TRUE);elsereturn(FALSE);}boolInc(charch)//判斷輸入的運(yùn)算符{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)//運(yùn)算關(guān)系的實(shí)行{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<<"不能運(yùn)算";break;} return0;}charCompare(charx,charch)//字符之間優(yōu)先權(quán)比較{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<<"請輸入一個(gè)表達(dá)式串（以=結(jié)束）"<<endl; cout<<"-----------------------------------"<<endl;charch;intw=0,q=0,y=0,z=0,m=0;//w=0表示無負(fù)號輸入，q=0表示無數(shù)字輸入，y=0表示有字符輸入，z=0表示無括號輸入，m=0表示無負(fù)括號標(biāo)記 floatn=0,v,a,b; charop;ch=getchar();if(!Ins(ch)){if(ch=='(')z=1;elseif(ch=='-'){w=1;ch=getchar();}//記錄輸入負(fù)號else{ cout<<endl;cout<<"您輸入的表達(dá)式有誤【(1)表達(dá)式不能以運(yùn)算符（除取反外）開頭】，請重新輸入!"<<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;//記錄負(fù)的左括號ch=getchar();continue;}elseif(ch=='-'){w=0;ch=getchar();}/*else{ cout<<endl;cout<<"您輸入的表達(dá)式有誤【(2)表達(dá)式中有不符合要求的運(yùn)算】，請重新輸入!"<<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;}}//表達(dá)式中有負(fù)號和括號時(shí)的運(yùn)算}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<<"您輸入的表達(dá)式有誤【(2)表達(dá)式中有運(yùn)算符位置錯(cuò)誤】，請重新輸入!"<<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ùn)算符的優(yōu)先級大于字符棧頂運(yùn)算符優(yōu)先級，將此運(yùn)算符進(jìn)棧y=1;z=0;ch=getchar();break;case'>':Pop(&TA,&op);//目前輸入運(yùn)算符的優(yōu)先級小于字符棧頂運(yùn)算符//優(yōu)先級，將棧頂運(yùn)算符出棧Pop(&TB,&b);//并且將數(shù)字棧的a,b出棧進(jìn)行運(yùn)算Pop(&TB,&a);if(op=='/'&&b==0){ cout<<endl;cout<<"您輸入的表達(dá)式有誤（分子不能為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);//將運(yùn)算結(jié)果壓進(jìn)數(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<<"您輸入的表達(dá)式有誤（不能出現(xiàn)非法字符），請重新輸入!"<<endl; cout<<"----------------------------------------"<<endl;fflush(stdin);ClearStack(&TA);ClearStack(&TB);Caculator();exit(1);}}v=GetTop(TB); cout<<"--------------------------------------------"<<endl; cout<<"計(jì)算結(jié)果為："<<endl;cout<<v<<endl; cout<<"--------------------------------------------"<<endl; system("pause"); cout<<"--------------------------------------------"<<endl; cout<<"請選擇:"<<endl; cout<<"1.進(jìn)入系統(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<<"-------------歡迎使用算術(shù)表達(dá)式求解系統(tǒng)!----------------"<<endl; cout<<endl; cout<<"-----------------------------------------"<<endl; cout<<"1.進(jìn)入系統(tǒng)"<<endl; cout<<"2.退出系統(tǒng)"<<endl; cout<<"-----------------------------------------"<<endl; cin>>c; switch(c) { case1:fflush(stdin); ClearStack(&TA);ClearStack(&TB); Ca