計算機科學與信息工程學院數據結構課程設計設計題目：簡單計算器 專 業 計算機軟件 班 級 計軟2班 小組成員 蔡松佐 陳吉院 王希 劉軍 符錦柏 曾祖濱 劉一霖 指導教師 張顯全 2010 年 12 月 25 日數據結構分工情況組長：蔡松佐組員：曾祖濱、陳吉院、符錦柏、劉軍、劉一霖、王希王希：負責設計程序的整體框架（定義數據結構，編寫主函數）評分：90分符錦柏：負責編寫棧的代碼評分：95分蔡松佐：負責編寫計算算術表達式的代碼評分：95分陳吉院：負責編寫比較符號優先級的代碼評分：90分曾祖濱：負責將所有代碼整合成一個完整的程序評分：88分劉軍：負責寫實驗報告評分：90分劉一霖：負責測試程序，看其是否具有良好的健壯性評分：88分簡單計算器一 基本功能描述簡單的計算器的功能是對基本的加、減、乘、除、四則運算，可對輸入的操作數，包括整數，小數等進行運算。二 設計思路本程序主要是采用棧的理論知識，主要用到兩個結構體棧，一個用來轉化表達式，一個用來計算表達式。區別就在于一個存儲字符，一個存儲浮點。首先，用一個字符數組來存儲用戶輸入的中綴表達式。然后用棧來把這個表達式轉化為后綴表達式，轉化時要進行符號優先級比較，這里將*/的優先級定為2，+-定為1，括號和=定為0。具體思想如下：例如用戶輸入了1+2*3=，將其存放入一個字符數組中。先在棧的底部存放一個=號符，用作符號優先級比較。首先將1存放到另外一個字符數組s1中，再將+號入棧。入棧的同時與底部的=比較優先級，+的優先級高于=，所以不出棧，之后將2存放入s2中，然后再將*入棧，入棧的同時與+比較符號優先級，*比+高，所以不出棧。再將3存入s2中。之后將棧中不是=的運算符都彈出棧，并依次存入s2中。所以s2中的表達式為123*+。之后進行計算，計算時用到浮點棧。首先將s2中的字符依次入棧，遇到運算符時進行計算。所以將123入棧后，再將*入棧的同時，將前面兩個數字進行運算，算出結果為6并存入棧中，之后再將+入棧，再與1進行運算，結果即為7，然后輸出結果。三 概要設計1，子函數功能struct Stack用來轉化表達式的機構體棧。Struct FStack用來計算表達式的結構體棧void InitStack(Stack &s)初始化結構體棧void InitFStack(FStack &s)初始化結構體棧char GetTop(Stack s)獲取棧頂數據void IncrementStackSize(Stack &s)為棧擴充ncrementsize個存儲空間void IncrementFStackSize(FStack &s)為棧擴充ncrementsize個存儲空間void Push(Stack &s,char e)第一個棧入棧操作void PushF(FStack &s,float e)第二個棧入棧操作bool Empty(Stack s)判斷第一個棧是否為空。bool EmptyF(FStack s)判斷第二個棧是否空char Pop(Stack &s)表達式出棧float PopF(FStack &s)計算的數據出棧int Precede(char op)確定優先級的函數void Change(char *s1,char *s2)改變兩個字符串的儲存位置float Compute(char *s2)實現數據的運算2 函數的調用 主函數棧的建立Stack，FStackChange(str1,str2)計算表達式Compute(str2)InitFStack(S);PushF(S,x)PopF(S)輸出cin.getline(str1,2);3 測試數據及測試結果(1)測試 1+2+3=6(2) 測試2*4=8(3)測試 3/2=1.5(4)測試(1+2)*3=9四 程序代碼#include #include #include #include #include #include struct Stack /轉換表達式char *elem;int top;int stacksize;int incrementsize;struct FStack /計算float *elem;int top;int stacksize;int incrementsize;void InitStack(Stack &s)s.elem=new char100;s.top=-1;s.stacksize=100;s.incrementsize=10;void InitFStack(FStack &s)s.elem=new float100;s.top=-1;s.stacksize=100;s.incrementsize=10;char GetTop(Stack s)return s.elems.top;void IncrementStackSize(Stack &s)char *a=new chars.stacksize+s.incrementsize;for(int i=0;i=s.top;i+)ai=s.elemi;delete s.elem;s.elem=a;s.stacksize+=s.incrementsize;void IncrementFStackSize(FStack &s)float *a=new floats.stacksize+s.incrementsize;for(int i=0;i Precede(ch) /優先級()函數返回運算符形參的優先級s2j+ = w;Pop(R);w = GetTop(R);Push(R,ch);ch = s1+i;else /此處為數字或小數點字符的處理while (isdigit(ch) | ch = .)s2j+ = ch;ch = s1+i;s2j+ = ; /被轉換后的每個數值后放一個空格/-ch = Pop(R);while (ch != =)s2j+ = ch;ch = Pop(R);s2j+ = =; /加入字符串結束符s2j+ = 0;float Compute(char *s2)FStack S; /用S棧存儲操作數和中間計算結果InitFStack(S);istrstream ins(s2); /把s2定義為輸入字符串流對象inschar ch; /用于輸入字符float x; /用于輸入浮點數insch;while (ch != =)switch (ch)case +:x = PopF(S) + PopF(S);break;case -:x = PopF(S);x = PopF(S) - x;break;case *:x = PopF(S) * PopF(S);break;case /:x = PopF(S);x = PopF(S) / x;break;default:ins.putback(ch);insx;PushF(S,x);insch;if (!EmptyF(S)x = PopF(S);if (EmptyF(S) /如果棧中只有一個值那一定是結果return x;void main()/主程序FStack s;char a10;float b,c;char str150,str250; /暫時存儲表達式char j=y;cout *歡迎使用本計算器*endlendl;haha:while(j=Y|j=y)int i=0,m=0,n=0,k=0,l=0,q=0,p=0;cout 請輸入一個以=字符結束的中綴算術表達式：endlendl;cin.getline(str1,sizeof(str1);while(str1i!=0)i+;if(str1i-1!=)cout表達式錯誤.請重新輸入.endlendl;goto haha;i=0;while(str1i!=0)if(str1i=0&str1i-1=/)cout表達式錯誤.請重新輸入.endlendl;goto haha;i+;i=0;while(str1i!=0)if(str1i=()m+;if(str1i=)n+;if(str1i=)k+;if(str1i=)l+;if(str1i=)q+;if(str1i=)p+;i+;if(m!=n | k!=l | q!=p)cout表達式錯誤.請重新輸入.endlendl;goto haha;Change(str1,str2); /處理結果coutn求值結果為： str1Compute(str2)endl;cout是否繼續 ：(Y/N)j;cin.getline(str1,2);coutendl *感謝使用本計算器*endl;五 課程設計總結1 收獲通過這次課程設計，更進一步了解了棧的原理和應用，同時也鍛煉了數據結構在實際中的熟練運用。2 心得體會在這次數據結構設計中遇到了很多實際性的問題，在實際設計中才發現，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯誤思維。通過這次設計，我懂得了學習的重要性，了解到理論知識與