數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)表達(dá)式求值

XXXXXX大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告班級(jí)：學(xué)號(hào)：姓名：指導(dǎo)老師：

目錄一算術(shù)表達(dá)式求值需求分析程序的重要功能程序運(yùn)營(yíng)平臺(tái)數(shù)據(jù)結(jié)構(gòu)算法及時(shí)間復(fù)雜度測(cè)試用例程序源代碼二感想體會(huì)與總結(jié)算術(shù)表達(dá)式求值一、需求分析一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界線符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界線符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程運(yùn)用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。二、程序的重要功能（1）從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出對(duì)的的結(jié)果。（2）顯示輸入序列和棧的變化過(guò)程。三、程序運(yùn)營(yíng)平臺(tái)VisualC++6.0版本四、數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為棧。（1）運(yùn)算符棧部分：structSqStack//定義棧{char*base;//棧底指針char*top;//棧頂指針intstacksize;//棧的長(zhǎng)度};intInitStack(SqStack&s)//建立一個(gè)空棧S{if(!(s.base=(char*)malloc(50*sizeof(char))))exit(0);s.top=s.base;s.stacksize=50;returnOK;}charGetTop(SqStacks,char&e)//運(yùn)算符取棧頂元素{if(s.top==s.base)//棧為空的時(shí)候返回ERROR{ printf("運(yùn)算符棧為空!\n"); returnERROR;}else e=*(s.top-1);//棧不為空的時(shí)候用e做返回值，返回S的棧頂元素，并返回OKreturnOK;}intPush(SqStack&s,chare)//運(yùn)算符入棧{if(s.top-s.base>=s.stacksize) { printf("運(yùn)算符棧滿!\n"); s.base=(char*)realloc(s.base,(s.stacksize+5)*sizeof(char));//棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間if(!s.base)exit(OVERFLOW); s.top=s.base+s.stacksize;s.stacksize+=5; } *(s.top)++=e;//把e入棧 returnOK;}intPop(SqStack&s,char&e)//運(yùn)算符出棧{ if(s.top==s.base)//棧為空棧的時(shí)候，返回ERROR { printf("運(yùn)算符棧為空!\n"); returnERROR; }else { e=*--s.top;//棧不為空的時(shí)候用e做返回值，刪除S的棧頂元素，并返回OK returnOK; }}intStackTraverse(SqStack&s)//運(yùn)算符棧的遍歷{ char*t; t=s.base; if(s.top==s.base) { printf("運(yùn)算符棧為空!\n");//棧為空棧的時(shí)候返回ERROR returnERROR; } while(t!=s.top) { printf("%c",*t);//棧不為空的時(shí)候依次取出棧內(nèi)元素t++; }returnERROR;}數(shù)字棧部分：structSqStackn//定義數(shù)棧{int*base;//棧底指針int*top;//棧頂指針intstacksize;//棧的長(zhǎng)度};intInitStackn(SqStackn&s)//建立一個(gè)空棧S{s.base=(int*)malloc(50*sizeof(int));if(!s.base)exit(OVERFLOW);//存儲(chǔ)分派失敗s.top=s.base;s.stacksize=50;returnOK;}intGetTopn(SqStackns,int&e)//數(shù)棧取棧頂元素{if(s.top==s.base){ printf("運(yùn)算數(shù)棧為空!\n");//棧為空的時(shí)候返回ERROR returnERROR;}else e=*(s.top-1);//棧不為空的時(shí)候，用e作返回值，返回S的棧頂元素，并返回OKreturnOK;}intPushn(SqStackn&s,inte)//數(shù)棧入棧{if(s.top-s.base>=s.stacksize) { printf("運(yùn)算數(shù)棧滿!\n");//棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間 s.base=(int*)realloc(s.base,(s.stacksize+5)*sizeof(int));if(!s.base)exit(OVERFLOW); s.top=s.base+s.stacksize;//插入元素e為新的棧頂元素s.stacksize+=5; } *(s.top)++=e;//棧頂指針變化 returnOK;}intPopn(SqStackn&s,int&e)//數(shù)棧出棧{ if(s.top==s.base) { printf("運(yùn)算符棧為空!\n");//棧為空棧的視時(shí)候，返回ERROR returnERROR; }else { e=*--s.top;//棧不空的時(shí)候，則刪除S的棧頂元素，用e返回其值，并返回OK returnOK; }}intStackTraversen(SqStackn&s)//數(shù)棧遍歷{ int*t; t=s.base; if(s.top==s.base) { printf("運(yùn)算數(shù)棧為空!\n");//棧為空棧的時(shí)候返回ERROR returnERROR; } while(t!=s.top) { printf("%d",*t);//棧不為空的時(shí)候依次輸出t++; }returnERROR;}五、算法及時(shí)間復(fù)雜度1、算法：建立兩個(gè)不同類(lèi)型的空棧，先把一個(gè)‘#’壓入運(yùn)算符棧。輸入一個(gè)算術(shù)表達(dá)式的字符串（以‘#’結(jié)束），從第一個(gè)字符依次向后讀，把讀取的數(shù)字放入數(shù)字棧，運(yùn)算符放入運(yùn)算符棧。判斷新讀取的運(yùn)算符和運(yùn)算符棧頂?shù)眠\(yùn)算符號(hào)的優(yōu)先級(jí)，以便擬定是運(yùn)算還是把運(yùn)算符壓入運(yùn)算符棧。最后兩個(gè)‘#’碰到一起則運(yùn)算結(jié)束。數(shù)字棧頂?shù)臄?shù)字就是規(guī)定的結(jié)果。2、時(shí)間復(fù)雜度：O(n)數(shù)據(jù)壓縮存儲(chǔ)棧，其操作重要有：建立棧intPush(SeqStack*S,charx)入棧intPop(SeqStack*S,charx)出棧。以上各操作運(yùn)算的平均時(shí)間復(fù)雜度為O(n)，其重要時(shí)間是花費(fèi)在輸入操作。測(cè)試用例如圖所示。最終結(jié)果如圖所示：源代碼/**************************************************************************************************第七題算術(shù)表達(dá)式求值[問(wèn)題描述]一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界線符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界線符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程運(yùn)用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。[基本規(guī)定]（1）從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出對(duì)的的結(jié)果。（2）顯示輸入序列和棧的變化過(guò)程。***************************************************************************************************/#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<conio.h>#include<ctype.h>#defineOK1#defineERROR0#defineSTACK_INIT_SIZE100//#defineSTACKINCREMENT10//========================================================//以下定義兩種棧，分別存放運(yùn)算符和數(shù)字//========================================================//*******************運(yùn)算符棧部分*************************structSqStack//定義棧{char*base;//棧底指針char*top;//棧頂指針intstacksize;//棧的長(zhǎng)度};intInitStack(SqStack&s)//建立一個(gè)空棧S{if(!(s.base=(char*)malloc(50*sizeof(char))))exit(0);s.top=s.base;s.stacksize=50;returnOK;}charGetTop(SqStacks,char&e)//運(yùn)算符取棧頂元素{if(s.top==s.base)//棧為空的時(shí)候返回ERROR{ printf("運(yùn)算符棧為空!\n"); returnERROR;}else e=*(s.top-1);//棧不為空的時(shí)候用e做返回值，返回S的棧頂元素，并返回OKreturnOK;}intPush(SqStack&s,chare)//運(yùn)算符入棧{if(s.top-s.base>=s.stacksize) { printf("運(yùn)算符棧滿!\n"); s.base=(char*)realloc(s.base,(s.stacksize+5)*sizeof(char));//棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間if(!s.base)exit(OVERFLOW); s.top=s.base+s.stacksize;s.stacksize+=5; } *(s.top)++=e;//把e入棧 returnOK;}intPop(SqStack&s,char&e)//運(yùn)算符出棧{ if(s.top==s.base)//棧為空棧的時(shí)候，返回ERROR { printf("運(yùn)算符棧為空!\n"); returnERROR; }else { e=*--s.top;//棧不為空的時(shí)候用e做返回值，刪除S的棧頂元素，并返回OK returnOK; }}intStackTraverse(SqStack&s)//運(yùn)算符棧的遍歷{ char*t; t=s.base; if(s.top==s.base) { printf("運(yùn)算符棧為空!\n");//棧為空棧的時(shí)候返回ERROR returnERROR; } while(t!=s.top) { printf("%c",*t);//棧不為空的時(shí)候依次取出棧內(nèi)元素t++; }returnERROR;}//**********************數(shù)字棧部分***************************structSqStackn//定義數(shù)棧{int*base;//棧底指針int*top;//棧頂指針intstacksize;//棧的長(zhǎng)度};intInitStackn(SqStackn&s)//建立一個(gè)空棧S{s.base=(int*)malloc(50*sizeof(int));if(!s.base)exit(OVERFLOW);//存儲(chǔ)分派失敗s.top=s.base;s.stacksize=50;returnOK;}intGetTopn(SqStackns,int&e)//數(shù)棧取棧頂元素{if(s.top==s.base){ printf("運(yùn)算數(shù)棧為空!\n");//棧為空的時(shí)候返回ERROR returnERROR;}else e=*(s.top-1);//棧不為空的時(shí)候，用e作返回值，返回S的棧頂元素，并返回OKreturnOK;}intPushn(SqStackn&s,inte)//數(shù)棧入棧{if(s.top-s.base>=s.stacksize) { printf("運(yùn)算數(shù)棧滿!\n");//棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間 s.base=(int*)realloc(s.base,(s.stacksize+5)*sizeof(int));if(!s.base)exit(OVERFLOW); s.top=s.base+s.stacksize;//插入元素e為新的棧頂元素s.stacksize+=5; } *(s.top)++=e;//棧頂指針變化 returnOK;}intPopn(SqStackn&s,int&e)//數(shù)棧出棧{ if(s.top==s.base) { printf("運(yùn)算符棧為空!\n");//棧為空棧的視時(shí)候，返回ERROR returnERROR; }else { e=*--s.top;//棧不空的時(shí)候，則刪除S的棧頂元素，用e返回其值，并返回OK returnOK; }}intStackTraversen(SqStackn&s)//數(shù)棧遍歷{ int*t; t=s.base; if(s.top==s.base) { printf("運(yùn)算數(shù)棧為空!\n");//棧為空棧的時(shí)候返回ERROR returnERROR; } while(t!=s.top) { printf("%d",*t);//棧不為空的時(shí)候依次輸出t++; }returnERROR;}//========================================================//以下定義函數(shù)//========================================================intIsoperator(charch)//判斷是否為運(yùn)算符，分別將運(yùn)算符和數(shù)字進(jìn)入不同的棧{ switch(ch) { case'+': case'-': case'*': case'/': case'(': case')': case'#': return1; default: return0; }}intOperate(inta,charop,intb)//運(yùn)算操作{ intresult; switch(op) { case'+': result=a+b; break; case'-': result=a-b; break; case'*': result=a*b; break; case'/': result=a/b; break; } returnresult;}charPrecede(charch1,charch2)//運(yùn)算符優(yōu)先級(jí)的比較{charp;switch(ch1){case'+':case'-': if(ch2=='+'||ch2=='-'||ch2==')'||ch2=='#')p='>';//ch1運(yùn)算符的優(yōu)先級(jí)小于ch2運(yùn)算符 elsep='<'; break;case'*':case'/': if(ch2=='(')p='<'; elsep='>'; break;case'(': if(ch2==')') p='='; elseif(ch2=='#') { printf("表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!\n"); exit(0); } else p='<'; break; case')': if(ch2=='(') { printf("表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!\n"); exit(0); } else p='>'; break;case'#': if(ch2==')'){ printf("表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!\n"); exit(0); } elseif(ch2=='#') p='='; else p='<'; break;}returnp;}//========================================================//以下是求值過(guò)程//========================================================intEvaluateExpression()//參考書(shū)p53算法3.4{ inta,b,temp,answer;charch,op,e;char*str;intj=0;SqStacknOPND;//OPND為運(yùn)算數(shù)字棧SqStackOPTR;//OPTR為運(yùn)算符棧InitStack(OPTR);Push(OPTR,'#');//,所以此棧底是'#'，由于運(yùn)算符棧以'#'作為結(jié)束標(biāo)志InitStackn(OPND);//printf("\n\n按任意鍵開(kāi)始求解:\n\n");//ch=getch();printf("\n請(qǐng)輸入表達(dá)式并以'#'結(jié)束:\n");str=(char*)malloc(50*sizeof(char));gets(str);ch=str[j];//ch是字符型的，而e是整型的整數(shù)j++;GetTop(OPTR,e);//e為棧頂元素返回值while(ch!='#'||e!='#'){ if(!Isoperator(ch))//碰到數(shù)字,轉(zhuǎn)換成十進(jìn)制并計(jì)算 { temp=ch-'0';//將字符轉(zhuǎn)換為十進(jìn)制數(shù) ch=str[j]; j++; while(!Isoperator(ch)) { temp=temp*10+ch-'0';//將逐個(gè)讀入運(yùn)算數(shù)的各位轉(zhuǎn)化為十進(jìn)制數(shù) ch=str[j]; j++; } Pushn(OPND,temp); } elseif(Isoperator(ch))//判斷是否是運(yùn)算符,不是運(yùn)算符則進(jìn)棧 switch(Precede(e,ch)){case'<':Push(OPTR,ch);//棧頂元素優(yōu)先權(quán)低 ch=str[j++]; printf("\n\n運(yùn)算符棧為：\n");//輸出棧，顯示棧的變化 StackTraverse(OPTR); printf("\n運(yùn)算數(shù)棧為：\n"); StackTraversen(OPND); break; case'=':Pop(OPTR,op);//脫括號(hào)并接受下一字符 ch=str[j++]; printf("\n\n運(yùn)算符棧為：\n"); StackTraverse(OPTR); printf("\n數(shù)棧為：\n"); StackTraversen(OPND); break; case'>':Pop(OPTR,op);//彈出最上面兩個(gè)，并運(yùn)算，把結(jié)果進(jìn)棧 Popn(OPND,b); Popn(OPND,a); Pushn(OPND,Operate(a,op,b)); printf("\n\n運(yùn)算符棧為：\n"); StackTraverse(OPTR); printf("\n數(shù)棧為：\n"); StackTraversen(OPND);}else {printf("您的輸入有問(wèn)題，請(qǐng)檢查重新輸入!"); exit(0); } GetTop(OPTR,e);//取出運(yùn)算符棧最上面元素是否是'#'}//whileGetTopn(OPND,answer);//已輸出。數(shù)字棧最上面即是最終結(jié)果return