數(shù)據(jù)結構——算術表達式求值算法.doc

沈陽航空航天大學 課課 程程 設設 計計 報報 告告 課程設計名稱 數(shù)據(jù)結構課程設計數(shù)據(jù)結構課程設計 課程設計題目 算術表達式求值算法算術表達式求值算法 院 系 計算機學院 專 業(yè) 計算機科學與技術 班 級 學 號 姓 名 指導教師 丁國輝 完成日期 2013年01月11日 沈陽航空航天大學課程設計報告 目目 錄錄 第第 1 章章 概要設計概要設計 1 1 1 題目的內(nèi)容與要求 1 1 2 總體結構 1 第第 2 章章 詳細設計詳細設計 3 2 1 棧的順序存儲模塊 3 2 2 進棧模塊 3 2 3 出棧模塊 4 2 4 運算模塊 4 2 5 判斷優(yōu)先級模塊 5 2 6 處理表達式主體模塊 6 第第 3 章章 調(diào)試分析調(diào)試分析 8 第第 4 章章 運行結果運行結果 9 參考文獻參考文獻 11 附附 錄 程序清單 錄 程序清單 12 沈陽航空航天大學課程設計報告 第 1 章 概要設計 0 第 1 章 概要設計 1 1 題目的內(nèi)容與要求題目的內(nèi)容與要求 內(nèi)容 設計程序 其能夠求解任意給定算數(shù)表達式的值 算數(shù)表達式中的操 作符來自于集合 表達式允許包括小括號 表達式的輸入 以 作為結束標志 要求 1 利用棧結構實現(xiàn)表達式求值算法 即在約定的條件下 正確輸入表達 式 經(jīng)過程序的運行之后 給出表達式的值 2 系統(tǒng)利用 C 語言實現(xiàn) 3 獨立完成系統(tǒng)的設計 編碼和調(diào)試 1 2 總體結構總體結構 本程序主要分為六個模塊 主要算法模塊圖見圖 1 1 棧的順序存儲模塊 進棧模塊 出棧模塊 運算模塊 判斷優(yōu)先級模塊 處理表達式主體模塊 棧的 順序存儲模塊 分別建立兩個棧 第一個用來存儲運算符 第二個是用來存儲數(shù) 字 進棧模塊 運算符和數(shù)字分別存儲在運算符棧和數(shù)字棧中 以便運算時的調(diào) 用 出棧模塊 由于運算的需要 就必須把運算符和數(shù)字分別從運算符棧和數(shù)字 棧中取出來 運算模塊 程序在遇到運算符的時候 根據(jù)此模塊的要求進行運算 判斷優(yōu)先級模塊 找出棧頂算符和即將入棧算符的對應的下標 然后根據(jù)算符間 的優(yōu)先關系表判斷出算符的優(yōu)先關系 處理表達式主體模塊 結合運算模塊和判 斷優(yōu)先級模塊 對表達式進行系統(tǒng)處理 求出算數(shù)表達式的值 沈陽航空航天大學課程設計報告 第 1 章 概要設計 1 算術表達式求值算法 出 棧 模 塊 判 斷 優(yōu) 先 級 模 塊 處 理 表 達 式 主 體 模 塊 棧 的 順 序 存 儲 模 塊 運 算 模 塊 進 棧 模 塊 圖圖 1 1 主要算法模塊圖主要算法模塊圖 沈陽航空航天大學課程設計報告 第 2 章 詳細設計 2 第 2 章 詳細設計 在本次課程設計中 我們用到了棧這個重要的數(shù)據(jù)結構 在實現(xiàn)程序的功能 的時候 有很多重要的程序段是涉及棧方面的 有棧的結構建立 入棧 出棧 另外還有就是對表達式進行運算 判斷運算符的優(yōu)先級 對表達式的主體進行處 理 重要的程序段如下 2 1 棧的順序存儲模塊棧的順序存儲模塊 本課程設計是通過棧為載體來實現(xiàn)程序的功能的 因此棧結構的建立是必不 可少的 分別建立兩個棧 第一個用來存儲運算符 第二個用來存儲數(shù)字 2 2 進棧模塊進棧模塊 主要是把運算符和數(shù)字分別存儲在運算符棧和數(shù)字棧里面 首先判斷棧是否 滿 若不滿就進棧 把 e 插入為新的棧頂元素 否則就追加存儲空間 流程圖如 圖 2 1 所示 FT 開始 判斷棧是否滿 追加存儲空間e 進棧為新的棧頂元素 結束 圖圖 2 12 1 進棧進棧模塊流程圖模塊流程圖 沈陽航空航天大學課程設計報告 第 2 章 詳細設計 3 2 3 出棧模塊出棧模塊 主要是把運算符和數(shù)字分別從運算符棧和數(shù)字棧中取出來 由于運算的需要 此時就必須把運算符和數(shù)字從棧中取出來 即出棧 運算符和數(shù)字的出棧 是先 取出棧頂元素an 由于取出元素之后 原先的棧頂元素的位置為空了 此時an 1就 成了棧頂元素了 所以原先的棧頂指針就減一 指向現(xiàn)在的棧頂元素an 1 第一個 函數(shù)是運算符的出棧 第二個函數(shù)是數(shù)字的出棧 首先判斷棧是否為空 若棧不 空 則刪除S的棧頂元素 用e返回其值 否則返回ERROR 流程圖如圖2 2所示 FT 開始 判斷棧是否空 返回 ERROR棧頂元素出棧 結束 圖圖2 22 2 出棧出棧模塊流程圖模塊流程圖 2 4 運算模塊運算模塊 當程序在遇到運算符的時候 就要進行運算 函數(shù)中a和b就是代表數(shù)字 而 theta就是代表運算符 當出棧時棧頂元素是 加 程序就執(zhí)行加法運算 最后的結果是a和b兩數(shù)之和 當出棧時棧頂元素是 減 程序就執(zhí)行減法 運算 最后的結果是a和b兩數(shù)之差 當出棧時棧頂元素是 乘 程序就執(zhí) 沈陽航空航天大學課程設計報告 第 2 章 詳細設計 4 行乘法運算 最后的結果是a和b兩數(shù)之積 當出棧時棧頂元素是 除 程 序就執(zhí)行除法運算 最后的結果是a和b兩數(shù)之商 函數(shù)的返回值就是函數(shù)最后的 結果 流程圖如圖2 3所示 default case 開始 theta 運算符 a b a b a b a b錯誤 結束 圖圖2 32 3 運算運算模塊流程圖模塊流程圖 2 5 判斷優(yōu)先級模塊判斷優(yōu)先級模塊 由于我們輸入的是四則運算 因此就不得不考慮算符的優(yōu)先級問題 先調(diào)用 函數(shù)ReturnOpOrd 找出棧頂算符和即將入棧算符的對應的下標 然后再調(diào)用 precede 函數(shù) 根據(jù)算符間的優(yōu)先關系表 如表2 4所示 判斷出算符的優(yōu)先關系 a1a2 a1的優(yōu)先權高于 a2 上述函數(shù)就是判斷優(yōu)先級的函數(shù) 經(jīng)過運算之后 函數(shù)返回值即為優(yōu)先權高 低 沈陽航空航天大學課程設計報告 第 2 章 詳細設計 5 a2 a1 T 開始 輸入表達式 c GetTop OPTR e e 不是算符 數(shù)字進 OPND 棧 存儲數(shù) 字的棧 運算符進 OPTR 棧 存儲算符 的棧 調(diào)用 ReturnOpOrd 和 precede 函數(shù)判 斷優(yōu)先關系 Pop OPT R x c 出 棧 Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b return GetTop O PND d d 結束 圖圖 2 52 5 處理表達式主體處理表達式主體模塊模塊流程圖流程圖 沈陽航空航天大學課程設計報告 第 3 章 調(diào)試分析 7 第 3 章 調(diào)試分析 1 問題 由于輸入時的疏忽遺漏了 等 編譯時出現(xiàn)錯誤 解決方法 通過編譯器的錯誤提示進行修改 添加一些遺漏的信息 2 問題 在運行時提示庫函數(shù)名為未標識符 解決方法 通過編譯器的錯誤提示進行修改 缺少頭文件 添加所需的頭文件 3 問題 輸出的數(shù)只能在97以內(nèi) 而且只能輸入輸出整數(shù) 不能實現(xiàn)輸入輸出 小數(shù) 當輸入小數(shù)時出現(xiàn)錯誤 解決方法 規(guī)范輸入輸出格式 4 問題 操作數(shù)和運算符在一起發(fā)生沖突 當混合輸入數(shù)據(jù)和運算符 出現(xiàn) 異常 沒有結果 解決方法 使用兩個工作棧 一個存儲數(shù)字 一個存儲運算符 沈陽航空航天大學課程設計報告 第 4 章 使用說明 8 第 4 章 運行結果 運行操作及結果 1 顯示輸入表達式 以 號結束 沈陽航空航天大學課程設計報告 第 4 章 使用說明 9 2 正確輸入表達式 以 號結束 就能得到表達式的值 沈陽航空航天大學課程設計報告 參考文獻 10 參考文獻 1 嚴蔚敏 吳偉明 數(shù)據(jù)結構 C 語言版 M 北京 清華大學出版社 2007 2 王敬華 林萍 張清國 C 語言程序設計教程 M 第二版 北京 清華大學 出版社 2009 8 3 吳海燕 任午令 章志勇 數(shù)據(jù)結構 M 杭州 浙江大學出版社 2011 6 4 胡圣榮 周靄如 羅穗萍 數(shù)據(jù)結構教程與題解 M 北京 清華大學出版社 2011 9 5 譚浩強 C 程序設計試題匯編 M 北京 清華大學出版社 2006 3 6 李兵 崔虹燕 馬曉亭 C 語言程序設計 M 北京 科學出版社 2011 沈陽航空航天大學課程設計報告 附錄 11 附 錄 程序清單 include include include int InitStack StackChar char OPSET 7 float EvaluateExpression char k StackChar OPTR StackFloat OPND char T 20 float Data a b char theta c x str 2 沈陽航空航天大學課程設計報告 附錄 12 char e float d InitStack OPTR Push OPTR InitStack OPND c k strcpy T 0 while c GetTop OPTR e e if In c OPSET str 0 c str 1 0 strcat T str c if In c OPSET Data float atof T Push OPND Data strcpy T 0 else switch precede GetTop OPTR e e c case Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break return GetTop OPND d d float Operate float a unsigned char theta float b switch theta case return a b case return a b case return a b case 沈陽航空航天大學課程設計報告 附錄 14 return a b default return 0 int In char Test char TestOp int ReturnOpOrd char op char TestOp int i for i 0 i 7 i if op TestOp i return i return 0 char precede char A char B return str ReturnOpOrd A OPSET ReturnOpOrd B OPSET void main char k 100 float result printf 輸入表達式 以 號結束 n gets k result EvaluateExpression k printf 2f n result 沈陽航空航天大學課程設計報告 15 課程設計總結 課程設計總結 這次數(shù)據(jù)結構課程設計 從理論到實踐 讓我對數(shù)據(jù)結構有了更深刻的認 識 也學到了很多東西 不僅鞏固了以前所學過的知識 而且還學到了很多書 本上所沒有的內(nèi)容 我在此次課程設計中深刻體會到了要寫好一個程序必須弄 清它的最基本的思路 除此之外要有算法思路 會寫一些基本函數(shù) 編程不像 做其它事 它要求編程人員有非常縝密的思維 很好的整體把握能力和很好的 調(diào)試程序的能力等 也要特別注重細節(jié) 我在編寫程序過程中遇到了很多的問 題 一些基本的函數(shù)應用不熟練 讓我發(fā)現(xiàn)了自己的知識的匱乏 掌握的不夠 牢固 懂得了只學書本上的東西是遠遠不夠的 只有把所學的理論知識與實踐 相結合起來 才能真正的學到東西 才能提高自己的實際動手能力和獨立思考 能力 在程序運行成功的時候 我的心里是非常喜悅的 這些天的努力終于有了 回報 在以后的學習過程中要多了解一些