目錄1．前言 2
2．問題描述 3
3．總體設計 3
3.1 概要設計 3
3.1.1 資料結構的選擇 3
3.1.2 相關功能函式 3
3.1.3 函式模組呼叫關係 4
3.2詳細設計和編碼 5
4．執行與測試 9
4.1 上機除錯 9
4.2 演算法時間和空間效能分析 10
4.3程式執行測試結果 11
5. 總結與心得 13
5.1設計中難點的總結以及其它解決方案 13
5.2 實驗心得 14
6. 使用者使用說明 16
7. 參考文獻 16
8. 附錄1（源**清單） 16
9. 附錄2（成績評定表） 25
1.前言
課程設計是實踐性教學中的乙個重要環節，它以某一課程為基礎，它可以涉及和課程相關的各個方面，是一門獨立於課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用，理解和掌握課程的相關知識。《資料結構》是一門重要的專業基礎課，是計算機理論和應用的核心基礎課程。
在資料結構的學習和課程設計過程中，我發現它要求學生在資料結構的邏輯特性和物理表示、資料結構的選擇和應用、演算法的設計及其實現等方面，都必須加深對課程基本內容的理解。同時，在程式設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。對於我們專業來說，雖然說對技術要求不是特別高，但是在實際操作過程中，沒有足夠的專業知識對於程式設計來說是遠遠不可以達到要求的，所以對於這次的課程設計，我們必須要通過自己額外補充知識來完成它。
在這次的課程設計中我選擇的題目是表示式的求值演示。它的基本要求是：以字串行的形式從終端輸入語法正確的，不含變數的表示式。
利用算符優先關係，實現對算術四則混合運算表示式的求值，並演示在求值中運算子棧、運算數棧、輸入字元和主要操作的變化過程。表示式計算是實現程式語言的基本問題之一，也是棧的應用的乙個典型例子。設計乙個程式，演示用算符優先法對算術表示式求值的過程。
深入了解棧和佇列的特性，以便在解決實際問題中靈活運用它們，同時加深對這種結構的理解和認識。對於表示出棧在每執行乙個過程中都要輸出它的變化，這點我認為在程式設計中是比較困難的，以我自身的能力，是不可能在規定的時間內完成任務的，所以我參考了很多有價值的書籍來幫助我完成我的程式設計。
2.問題描述（問題分析和任務定義）
在計算機中，算術表示式由常量、變數、運算子和括號組成。由於不同的運算子具有不同的優先順序，又要考慮括號，因此，算術表示式的求值不可能嚴格地從左到右進行。因此，要求設計乙個程式，利用棧演示運算子優先法對算術表示式求值的過程，利用算符有限關係，實現對算數混合四則運算表示式的求值。
程式輸入：乙個算術表示式，由常量、運算子和括號組成（以字串形式輸入，不含變數 ）。為了簡化，運算元只能為浮點數，操作符為用表示結束。
程式輸出：表示式運算結果，運算子棧、運算數棧、輸入字元和主要操作變化過程。
測試資料：1024/(4*8) 、(20+2)*(6/2)（用於正確性檢測的合法輸入資料）
9/0用於健壯性檢測的非法輸入資料）
3.總體設計
3.1概要設計
3.1.1資料結構的選擇
任何乙個表示式都是由操作符，運算子和界限符組成的。我們分別用順序棧來寄存表示式的運算元和運算子。棧是限定於緊僅在表尾進行插入或刪除操作的線性表。
為了實現算符優先演算法，可以使用兩個工作棧。乙個稱做optr，用以寄存運算子；另乙個稱做opnd，用以寄存運算元或運算結果。首先置運算元棧為空棧，表示式起始符「＃」作為運算子棧的棧底元素，然後依次讀入表示式的每個字元，若是運算元則進入opnd棧，若是運算子，則和optr棧的棧頂運算子比較優先權後做相應操作，直至整個表示式求值完畢。
棧的抽象資料型別定義
adt sqstack
資料關係：r1=
約定其中ai端為棧底，an端為棧頂。
操作集合：見如下相關功能函式
}adt sqstack
3.1.2相關功能函式
運算子棧的功能函式
運算數棧的功能函式
算術表示式的相關功能函式
3.1.3函式模組呼叫關係
3.2詳細設計和編碼
首先本程式定義兩個順序棧：運算子棧（optr）和運算數棧（opnd）；
optr棧定義如下：
typedef structoptr_stack;
opnd棧定義如下：
typedef structopnd_stack;
然後是主要功能函式的詳細設計：
（1）char precede(char m,char n) 判斷運算子優先權，返回優先權高的
算符間的優先關係如下：
函式實現如下：
char precede(char m,char n)//運算子的優先順序比較
else if(n=='*'||n=='/')//輸入的符號為"*"、"/"
else if(n=='(')return'<';//輸入的符號為"(",則直接返回"<"
else if(n==')')//輸入的符號為")"
else輸入符號為其他
}（2）void evaluate(optr_stack &s1,opnd_stack &s2)以字串形式輸入算數表示式，根據是運算子還是運算數來判斷如何入棧
函式實現如下：
void evaluate(optr_stack &s1,opnd_stack &s2)
{ char c;
float t,e;
int n=0,i=1,j=0,k=0,l=0;
char ch[stack_init_size];
int s=1;
int flag=0,flag2=0;
float p1,p2;
char ch1;
optr_push(s1,'#');//將'#'入棧，作為低階運算子
cout<<"請輸入不含變數的表示式（以#結束!）：\n ";
cin>>ch;
c=ch[0];
cout<<"\n對表示式求值的操作過程如下："
<<"\nn"
<<"步驟\t運算子棧s1\t運算數棧s2\t字元表示式\t\t棧操作過程";
while(c!='#'||optr_gettop(s1)!='#')
{cout<<"\nn";
資料結構算術表示式求值實驗報告
目錄1 前言 1 2 概要設計 1 2.1 資料結構設計 1 2.2 演算法設計 1 2.3 adt描述 2 2.4 功能模組分析 2 3 詳細設計 3 3.1 資料儲存結構設計 3 3.2主要演算法流程圖 或演算法偽 3 4 軟體測試 6 5 心得體會 8 參考文獻 8 附錄 8 在計算機中，算術...
資料結構實驗 表示式求值
資料結構實驗 棧的應用 算術表示式求值 張雷2014年4月11日 實驗目的 1.掌握棧的特性和基本演算法。2.學習利用資料結構解決實際問題的方法。問題描述 表示式求值 計算乙個合法的算術表示式 含四則運算 小括號和正的浮點數 的值。若實驗1已完成了多項式的四則運算，則可以改為計算乙個多項式表示式 運...
實驗四算術表示式求值
源 include include include define plus 0 define minus 1 define power 2 define divide 3 define leftp 4 define righp 5 define startend 6 define digit 7 d...