【正文】 模擬計算器 學生姓名： **** 指導老師： **** 摘 要 本課程設計的課題是設計一個 模擬計算器的程序 ，能夠進行表達式的計算，并且表達式中可以包含 Abs()和 Sqrt()運算。在課程設計中，系統(tǒng)開發(fā)平臺為 Windows ，程序設計設計語言采用 C++，程序運行平臺為 Windows 或 *nix。本程序的關(guān)鍵就是表達式的分離和處理，在程序設計中，采用了將輸入的中綴表達式轉(zhuǎn)化為后綴表達式的方法，具有可靠的運行效率。本程序做到了對輸入的表達式（表達式可以包含浮點數(shù)并且 Abs()和 Sqrt()中可以嵌套子表達 式）進行判定表達式是否合法并且求出表達式的值的功能。經(jīng)過一系列的調(diào)試運行，程序?qū)崿F(xiàn)了設計目標，可以正確的處理用戶輸入的表達式，對海量級數(shù)據(jù)都能夠通過計算機運算快速解決。 關(guān)鍵詞 C++程序設計；數(shù)據(jù)結(jié)構(gòu)；表達式運算；棧；中綴表達式；后綴表達式；字符串處理；表達式合法判定； 目 錄 1 引 言 ............................................................ 3 課程設計目的 ................................................. 3 課程設計內(nèi)容 ................................................. 3 2 設計思路與方案 .................................................... 4 3 詳細實現(xiàn) .......................................................... 5 表達式的合 法判定 ............................................ 5 中綴表達式轉(zhuǎn)化為后綴表達式 .................................. 5 處理后綴表達式 .............................................. 7 表達式嵌套處理 .............................................. 8 4 運行環(huán)境與結(jié)果 .................................................... 9 運行環(huán)境 .................................................... 9 運行結(jié)果 .................................................... 9 5 結(jié)束語 ........................................................... 12 參考文獻 ........................................................... 13 附錄 1：模擬計算器源程序清單 ....................................... 14 1 引 言 本課程設計主要解決的是傳統(tǒng)計算器中，不能對表達式進行運算的問題，通過制作該計算器模擬程序，可以做到快速的求解表達式的值，并且能夠判定用戶輸入的表達式是否合法。該模擬計算器的核心部分就在用戶輸入的中綴表達式的轉(zhuǎn)化，程序中用到了“?！钡暮筮M先出的基本性質(zhì)。利用兩個“?！?，一個“數(shù)據(jù)?！?，一個“運算符棧”來把中綴表達式轉(zhuǎn)換成后綴表達式。最后 利用后綴表達式來求解表達式的值。該算法的復雜度為 O(n)，能夠高效、快速地求解表達式的值，提高用戶的效率。 課程設計目的 數(shù)據(jù)結(jié)構(gòu)主要是研究計算機存儲，組織數(shù)據(jù)，非數(shù)值計算程序設計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統(tǒng)工程等各種領(lǐng)域。學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中涉及的對象在計算機中表示出來并對它們進行處理。通 過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業(yè)素質(zhì)的提高。 模擬計算器程序主要利用了“?！边@種數(shù)據(jù)結(jié)構(gòu)來把中綴表達式轉(zhuǎn)化為后綴表達式，并且運用了遞歸的思想來解決 Abs()和 Sqrt()中嵌套表達式的問題，其中還有一些統(tǒng)計的思想來判定表達式是否合法的算法。 課程設計內(nèi)容 本次課程設計為計算器模擬程序，主要解決表達式計算的問題，實現(xiàn)分別按表達式處理的過程分解為幾個子過程，詳細的求解過程如下： 1 用戶輸入表達式。2 判定表達式是否合法。 3 把中綴表達式轉(zhuǎn)化為后綴表達式。 4 求出后綴表達式的 結(jié)果。 5 輸出表達式的結(jié)果。通過設計該程序，從而做到方便的求出一個表達式的值，而不需要一步一步進行運算。 2 設計思路與方案 本課程設計需要考慮許多的問題，首先是表達式的合法判斷，然后是字符串表達式提取分離的問題，核心部分就是中綴表達式轉(zhuǎn)化為后綴表達式。對于第一個問題，我是分步來判斷，首先表達式中是否含有其它非法字符，然后判斷括號是否合法，接著判斷運算法兩邊是否合法，比如除法時，除數(shù)不能為零。對于第二個問題，我是直接轉(zhuǎn)換的，從左到右遍歷中綴表達式，把數(shù)據(jù)全部取出來。對于核心問題，利用了“?！边@種“后進先出 ”的數(shù)據(jù)結(jié)構(gòu)， 利用兩個“?！保粋€“數(shù)據(jù)?！?，一個“運算符棧”來把中綴表達式轉(zhuǎn)換成后綴表達式。最后利用后綴表達式來求解表達式的值。 上面是數(shù)據(jù)處理的算法部分。本程序用戶界面總共分為 3 個模塊，分別是操作提示，數(shù)據(jù)輸入，數(shù)據(jù)輸出。如圖 所示。 圖 用戶界面 除了實現(xiàn)基本的功能外，我還增加了其它一些功能，比如支持輸入數(shù)據(jù)為浮點數(shù)，更重要的是本程序還支持表達式的嵌套運算，例如： A(1+2*S(2))我的實現(xiàn)方法是利用函數(shù)的遞歸調(diào)用來解決此問題，即把 1+2*S(2)看成一個子表達式，這個子表達式中 2 也看成子表達式。這樣使得程序的適用范圍更加的廣泛，適應性更強，能支持更復雜的表達式的運算。這也是本程序的優(yōu)點之一。 3 詳細實現(xiàn) 表達式的合法判定 表達式的合法判定過程 如圖 所示 圖 表達式的合法判定過程 首先是其它字符的判定，從左到右遍歷中綴表達式，看是否存在其它非法的。 然后是判定括號是否的匹配是否和合法，首先把“ (”對應為 1，相應的“ )”對應為 1。從左到右遍歷表達式，如果遇到括號就加 上其對應的值，用 sum 來保存其累加值。如果在中途出現(xiàn) sum 小于零的情況，即出現(xiàn)“ ..... )” 那么的情況，即非法。在遍歷的最后，還要判斷 sum 的值是否為零，如果為零就是合法，否則就是非法。代