《長沙理工大學數(shù)據(jù)結構棧的實現(xiàn)及應用算術表達式求值實驗報告.doc》由會員分享,可在線閱讀,更多相關《長沙理工大學數(shù)據(jù)結構棧的實現(xiàn)及應用算術表達式求值實驗報告.doc(13頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、批閱實 驗 報 告 年級 班號 學號 姓名 實驗名稱: 棧的實現(xiàn)及其應用:算術表達式的計算 實驗日期 2016年12月 2日實驗報告撰寫內(nèi)容一、實驗環(huán)境二、實驗目的三、實驗內(nèi)容四、數(shù)據(jù)結構與算法思想描述五、程序清單六、程序執(zhí)行結果及其分析計算機科學與技術系2016年制一、 實驗環(huán)境32位操作系統(tǒng)下的Window平臺 Microsoft Visual C+二、 實驗目的掌握棧的實現(xiàn)及使用三、 實驗內(nèi)容1.實現(xiàn)棧的存儲結構2.實現(xiàn)棧的基本操作的有關算法3.利用棧解決*算術表達式求值問題四、 數(shù)據(jù)結構與算法思想描述順序讀取中綴表達式:1、 當遇到數(shù)字時,將數(shù)字入數(shù)字棧2、 當遇到操作符時,與操作符棧
2、棧頂比較:If(當前操作符優(yōu)先級大于操作符棧棧頂?shù)膬?yōu)先級)If(非”)”操作符)將當前操作符進操作符棧;ElseWhile(操作符棧棧頂不等于”(“)取操作符棧棧頂及數(shù)字棧的兩個數(shù)進行運算,并將結果壓入數(shù)字棧;ElseIf(非(“操作符)While(操作符棧棧頂不等于”(“)取操作符棧棧頂及數(shù)字棧的兩個數(shù)進行運算,并將結果壓入數(shù)字棧;Continue;(直到當前操作符比棧頂操作符優(yōu)先級大)Else將當前操作符進操作符棧;3、 While(操作符棧非空)操作符棧棧頂及數(shù)字棧的兩個數(shù)進行運算,并將結果壓入數(shù)字棧;4、 在數(shù)字棧取最后結果并輸出。五、 程序清單/10*82+16.3+5*(5.2*5
3、+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666/100+(-100)-(-102) = 100/(2016-2017+(2015-2014) = 0/-1+(10)+100%102 = 0#include#include#include#include#include#includeusing namespace std;const int MAX = 105;typedef double Type;typedef structType TypeStackMAX;char charStackMAX;int TypeTop, charTop;St
4、ack;/初始化棧void InitStack(Stack *S)S-charTop = S-TypeTop = 0;/判斷charStack是否為空bool IsEmpty_Char(Stack S)return S.charTop = 0;/判斷TypeStack是否為空bool IsEmpty_Type(Stack S)return S.TypeTop = 0;/判斷charStack是否為滿bool IsFull_Char(Stack S)return S.charTop = MAX;/判斷TypeStack是否為滿bool IsFull_Type(Stack S)return S.T
5、ypeTop = MAX;void Push_Char(Stack *S, char ch)/charStack不為滿則入棧,否則輸出提示if(!IsFull_Char(*S)S-charStackS-charTop+ = ch;elsecout The CharStack Is Full! TypeStackS-TypeTop+ = a;elsecout The TypeStack Is Full! charTop-;return S-charStackS-charTop;elsecout The CharStack Is Empty! TypeTop-;return S-TypeStack
6、S-TypeTop;elsecout The TypeStack Is Empty! endl;return -1;char Top_Char(Stack S)if(!IsEmpty_Char(S)return S.charStack-S.charTop;elsecout The CharStack Is Empty! endl;return -1;Type Top_Type(Stack S)if(!IsEmpty_Type(S)return S.TypeStack-S.TypeTop;elsecout The TypeStack Is Empty! endl;return -1;Type C
7、alculate(Type left, Type right, char op)Type value = 0;switch(op)case +:value = left + right;break;case -:value = left - right;break;case *:value = left * right;break;case /:if(right != 0)value = left / right;elsecout 被除數(shù)不能為零! endl;break;case %:if(right != 0)value = (int)left % (int)right;elsecout 被
8、余數(shù)不能為零! = 0)while(right-)value *= left;elseright = -right;while(right-)value /= left;*/return value;void Computer(char *mid_equotion, Type len)Type right, left , result;char *p_mid_equotion = mid_equotion;char after_equotion = ;map Oper;Oper# = 1;Oper( = 2;Oper+ = 3;Oper- = 3;Oper* = 4;Oper/ = 4;Ope
9、r% = 4;Oper = 5;Oper) = 6;Stack MyStack;InitStack(&MyStack);Push_Char(&MyStack,#);char top_oper, current_oper;for(;*p_mid_equotion != 0;)top_oper = Top_Char(MyStack);current_oper = *p_mid_equotion;if(!Opercurrent_oper)Push_Type(&MyStack,strtod(p_mid_equotion, &p_mid_equotion);continue;/end ifelse/為操
10、作符if(Opercurrent_oper Opertop_oper)if(current_oper != )Push_Char(&MyStack,current_oper);elsewhile(top_oper != ()right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack)left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, Top_Char(MyStack);Pop_Char(&MyStack);top_oper = Top_Cha
11、r(MyStack);Pop_Char(&MyStack);/end else/end ifelseif(current_oper = ()Push_Char(&MyStack,current_oper);if(*(p_mid_equotion + 1) = -)Push_Type(&MyStack,0);elseright = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack)left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper)
12、;Pop_Char(&MyStack);continue;/end else/end elsep_mid_equotion+;/end fortop_oper = Pop_Char(&MyStack);while(top_oper != #)right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack)left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper);top_oper = Pop_Char(&MyStack);/cout
13、setprecision(6) nThe Result = (result = Pop_Type(&MyStack) endl;printf(The Result = %lfnn,(result = Pop_Type(&MyStack);int main()char sMAX = ;Type i = 0;cout s & strcmp(s,-1) != 0)Computer(s,strlen(s);cout 請輸入你要求值的表達式!(以-1結束)n;return 0;六、 程序執(zhí)行結果及其分析對 “+” , “-” , “*” , “/” , “%” , “” 運算的實現(xiàn)可運算多位數(shù)和小數(shù),求余,求平方,括號里包含負數(shù)如(-1),及首個數(shù)字為負數(shù)如-1+1