壹、概述
數據結構課程設計，要求學生在數據結構的邏輯特性和物理表示、數據結構的選擇和應用、算法的設計及其實現等方面，加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。
在這次的課程設計中我選擇的題目是算術表達式求值演示。表達式計算是實現程序設計語言的基本問題之壹，也是棧的應用的壹個典型例子。設計壹個程序，演示用算符優先法對算術表達式求值的過程。深入了解棧和隊列的特性，以便在解決實際問題中靈活運用它們，同時加深對這種結構的理解和認識。
二、 系統分析
1． 以字符列的形式從終端輸入語法正確的、不含變量的整數表達式。利用已知的算符優先關系，實現對算術四則混合運算表達式的求值，並仿照教科書的例子在求值中運算符棧、運算數棧、輸入字符和主要操作的變化過程。
2． 壹般來說，計算機解決壹個具體問題時，需要經過幾個步驟：首先要從具體問題抽象出壹個適當的數學模型，然後設計壹個解決此數學模型的算法，最後編出程序，進行測試，調試直至得到想要的答案。對於算術表達式這個程序，主要利用棧，把運算的先後步驟進行分析並實現簡單的運算！為實現算符優先算法，可以使用兩個棧，壹個用以寄存運算符，另壹個用以寄存操作數和運算結果。
3． 演示程序是以用戶於計算機的對話方式執行，這需要壹個模塊來完成使用者與計算機語言的轉化。 4． 程序執行時的命令：
本程序為了使用具體，采用菜單式的方式來完成程序的演示，幾乎不用輸入什麽特殊的命令，只需按提示輸入表達式即可。（要註意輸入時格式，否者可能會引起壹些錯誤） 5. 測試數據。
2
算術表達式求值演示
壹、概述
數據結構課程設計，要求學生在數據結構的邏輯特性和物理表示、數據結構的選擇和應用、算法的設計及其實現等方面，加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。
在這次的課程設計中我選擇的題目是算術表達式求值演示。表達式計算是實現程序設計語言的基本問題之壹，也是棧的應用的壹個典型例子。設計壹個程序，演示用算符優先法對算術表達式求值的過程。深入了解棧和隊列的特性，以便在解決實際問題中靈活運用它們，同時加深對這種結構的理解和認識。
二、 系統分析
1． 以字符列的形式從終端輸入語法正確的、不含變量的整數表達式。利用已知的算符優先關系，實現對算術四則混合運算表達式的求值，並仿照教科書的例子在求值中運算符棧、運算數棧、輸入字符和主要操作的變化過程。
2． 壹般來說，計算機解決壹個具體問題時，需要經過幾個步驟：首先要從具體問題抽象出壹個適當的數學模型，然後設計壹個解決此數學模型的算法，最後編出程序，進行測試，調試直至得到想要的答案。對於算術表達式這個程序，主要利用棧，把運算的先後步驟進行分析並實現簡單的運算！為實現算符優先算法，可以使用兩個棧，壹個用以寄存運算符，另壹個用以寄存操作數和運算結果。
3． 演示程序是以用戶於計算機的對話方式執行，這需要壹個模塊來完成使用者與計算機語言的轉化。 4． 程序執行時的命令：
本程序為了使用具體，采用菜單式的方式來完成程序的演示，幾乎不用輸入什麽特殊的命令，只需按提示輸入表達式即可。（要註意輸入時格式，否者可能會引起壹些錯誤） 5. 測試數據。
操作集合：
(1)void InitStack1(SqStack1 &S1);//聲明棧建立函數 (2)void InitStack2(SqStack2 &S2);//聲明棧建立函數
(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//確定如何入棧函數 (4)void Push1(SqStack1 &S1,char e);//聲明入棧函數 (5)void Push2(SqStack2 &S2,float e);//聲明入壓棧函數 (6)char GetTop1(SqStack1 &S1);//聲明取棧頂元素函數 (7)float GetTop2(SqStack2 &S2);//聲明取棧頂元素函數 (8)char Pop1(SqStack1 &S1);//聲明出棧函數 (9)float Pop2(SqStack2 &S2);//聲明出棧函數 (10)char Compare(char m,char n);//聲明比較函數
(11)float Operate(float a,char rheta,float b);//聲明運算函數 (12)void DispStack1(SqStack1 &S1);//從棧底到棧頂依次輸出各元素 (13)void DispStack2(SqStack2 &S2);//從棧底到棧頂依次輸出各元素 }ADT SqStack
結構分析:
棧中的數據節點是通過數組來存儲的。因為在C語言中數組是用下標從零開始的，因此我
們在調用他們的數據是要特別註意。指針變量的值要麽為空(NULL)，不指向任何結點；要麽其值為非空，即它的值是壹個結點的存儲地址。註意，當P為空值時，則它不指向任何結點，此時不能通過P來訪問結點，否則會引起程序錯誤。如果輸入的數字不符合題目要求，則會產生錯誤結果。
算法的時空分析：
時間和空間性能分析：時間上，對於含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復雜度為O(n)。空間上，由於是用數組來存儲輸入的表達式，用棧來存儲運算中的數據和運算符，而棧的本質也用到的數組，數組在定義時必須確定其大小。在不知表達式長度的情況下確定數組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。