數(shù)據(jù)結(jié)構(gòu)——算術(shù)表達(dá)式求值算法.doc

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