目錄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
在計算機中，算術表示式由常量、變數、運算子和括號組成。由於不同的運算子具有不同的優先順序，又要考慮括號，因此，算術表示式的求值不可能嚴格地從左到右進行。因而在程式設計時，借助棧實現。
演算法輸入：乙個算術表示式，由常量、變數、運算子和括號組成（以字串形式輸入）。為簡化，規定運算元只能為正整數，操作符為+、-*、/，用#表示結束。
演算法輸出：表示式運算結果。
演算法要點：設定運算子棧和運算數棧輔助分析算符優先關係。在讀入表示式的字串行的同時，完成運算子和運算數的識別處理，以及相應運算。
任何乙個表示式都是由操作符，運算子和界限符組成的。我們分別用順序棧來寄存表示式的運算元和運算子。棧是限定於緊僅在表尾進行插入或刪除操作的線性表。
順序棧的儲存結構是利用一組連續的儲存單元依次存放自棧底到棧頂的資料元素，同時附設指標top指示棧頂元素在順序棧中的位置，base為棧底指標，在順序棧中，它始終指向棧底，即top=base可作為棧空的標記，每當插入新的棧頂元素時，指標top增1，刪除棧頂元素時，指標top減1。
為了實現算符優先演算法。可以使用兩個工作棧。乙個稱為optr，用以寄存運算子，另乙個稱做opnd，用以寄存運算元或運算結果。
1.首先置運算元棧為空棧，表示式起始符」#」為運算子棧的棧底元素；
2.依次讀入表示式，若是操作符即進opnd棧，若是運算子則和optr棧的棧頂運算子比較優先權後作相應的操作，直至整個表示式求值完畢（即optr棧的棧頂元素和當前讀入的字元均為」#」）。
adt stack
資料物件：r1=
約定端為棧頂，端為棧底。
基本操作：
initstack(&s)
操作結果：構造乙個空棧s。
gettop(s)
初始條件：棧s已存在。
操作結果：用p返回s的棧頂元素。
push(&s，ch)
初始條件：棧s已存在。
操作結果：插入元素ch為新的棧頂元素。
pop(&s)
初始條件：棧s已存在。
操作結果：刪除s的棧頂元素。
in(ch)
操作結果：判斷字元是否是運算子，運算子即返回1。
precede(c1, c2)
初始條件：c1,c2為運算子。
操作結果：判斷運算子優先權，返回優先權高的。
operate(a,op,b)
初始條件：a,b為整數，op為運算子。
操作結果：a與b進行運算，op為運算子，返回其值。
num(n)
操作結果：返回運算元的長度。
evalexpr()
初始條件：輸入表示式合法。
操作結果：返回表示式的最終結果。
}adt stack
1.棧的基本功能。
initstack(stack *s) 和initstack2(stack2 *s)分別構造運算子棧與構造運算元棧，push(stack *s,char ch) 運算子棧插入ch為新的棧頂元素，push2(stack2 *s,int ch) 運算元棧插入ch為新的棧頂元素，pop(stack *s) 刪除運算子棧s的棧頂元素，用p返回其值，pop2(stack2 *s)刪除運算元棧s的棧頂元素，用p返回其值，gettop(stack s)用p返回運算子棧s的棧頂元素，gettop2(stack2 s) 用p返回運算元棧s的棧頂元素。
2.其它功能分析。
(1)in(char ch) 判斷字元是否是運算子功能，運算子即返回1，該功能只需簡單的一條語句即可實現，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。
(2) precede(char c1,char c2) 判斷運算子優先權功能，該函式判斷運算子c1,c2的優先權，具體優先關係參照表1。
(3) operate(int a,char op,int b)運算元用對應的運算子進行運算功能。運算結果直接返回。
(4) num(int n) 求運算元的長度功能，需要用itoa函式把int型轉換成字串型，strlen函式可求字元長度。
(5) evalexpr()主要操作函式運算功能。分析詳細見「3.詳細設計…3.2」。
因為表示式是由操作符，運算子和界限符組成的。如果只用乙個char型別棧，不能滿足2位以上的整數，所以還需要定義乙個int型別的棧用來寄存運算元。
/* 定義字元型別棧 */
typedef struct stack;
/* 定義整型棧 */
typedef struct stack2;
1. precede(char c1,char c2) 判斷運算子優先權，返回優先權高的。
算符間的優先關係如下：
表 1演算法偽**如下：
char precede(char c1,char c2)
switch(c2)
return (array[7*i+j]); /* 返回運算子array[7*i+j]為對應的c1,c2優先關係*/
}2. int evalexpr()主要操作函式。演算法概要流程圖：
利用該演算法對算術表示式3*(7-2)求值操作過程如下：
表2演算法偽**如下：
int evalexpr()//主要操作函式
else
switch(precede(gettop(optr),c)) }
1.執行成功後介面。
2.輸入正確的表示式後。
3.更改表示式，輸入有2位數的整數除錯。
這次課程設計讓我更加了解大一學到的c和這個學期學到的資料結構。課設題目要求不僅要求對課本知識有較深刻的了解，同時要求程式設計者有較強的思維和動手能力和更加了解程式設計思想和程式設計技巧。
這次課程設計讓我有乙個深刻的體會，那就是細節決定成敗，程式設計最需要的是嚴謹，如何的嚴謹都不過分，往往檢查了半天發現錯誤發生在某個括號，分號，引號，或者資料型別上。就像我在寫evalexpr()函式時，忘了指標的位址符值不用加*號，這一點小小的錯誤也耽誤了我幾十分鐘，所以說細節很重要。
程式設計時，也不要怕遇到錯誤，在實際操作過程中犯的一些錯誤還會有意外的收穫，感覺課程設計很有意思。在具體操作中這學期所學的資料結構的理論知識得到鞏固，達到課程設計的基本目的，也發現自己的不足之出，在以後的上機中應更加注意，同時體會到c語言具有的語句簡潔，使用靈活，執行效率高等特點。發現上機的重要作用，特別算術表示式有了深刻的理解。
資料結構實驗 表示式求值
資料結構實驗 棧的應用 算術表示式求值 張雷2014年4月11日 實驗目的 1.掌握棧的特性和基本演算法。2.學習利用資料結構解決實際問題的方法。問題描述 表示式求值 計算乙個合法的算術表示式 含四則運算 小括號和正的浮點數 的值。若實驗1已完成了多項式的四則運算，則可以改為計算乙個多項式表示式 運...
資料結構算術表示式求值課程設計
目錄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程式執行測試結...
實驗四算術表示式求值
源 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...