2019獨角獸企業重金招聘Python工程師標準>>>

=======================================

計算器 abacus 的下載地址：http://www.oschina.net/code/snippet_736932_13725

????? 如果你有關于 abacus 的問題或者建議，請發郵件至 zhoucosin@163.com。謝謝。

=======================================??

本節介紹一些問題以及如何設計計算器以解決這些問題。

程序的目標：

• 支持四則混合運算 ok.
  
• 支持數學函數，如三角函數、指對函數、組合數等 ok.
  
• 支持符號常量，如圓周率、自然對數的底數等? ok.
  
• 支持變量運算(并非符號計算) doing...
  
• 支持表達式函數（即含有變量的表達式作為函數） doing...
  
• 支持有控制流程的函數 wait for doing.
  

???? 首先確定程序的使用方式，目前只打算以命令行的方式運行程序，暫不考慮界面的問題，程序啟動后，用戶逐條輸入表達式以計算其值，每計算完一個表達式并顯示之后，程序將等待用戶輸入下一個表達式，直到用戶輸入"quit" 退出程序。

????? 表達式在本質上就是一個由運算符、運算數、標點符號這些表達式元素組成的序列，所以問題的關鍵在于解釋這些序列的數學意義。

????? 首先需要從字符串形式的表達式中提取各個表達式元素（運算符、運算數、標點符號：主要是括號和逗號），并將這些表達式元素依次保存到一個線性的數據結構中去，這稱為詞法分析。在詞法分析之前，應該進行一些預處理，比如檢查括號是否匹配。而在詞法分析之后也應有一些后處理，比如對標識符作進一步處理，詞法分析器只能識別出標識符，它并不知道一個標識符到底是一個函數的名字還是一個符號常量，需要做相應的更換。

????? 經過詞法分析之后，我們就得到了一個由表達式元素所組成的序列了，而表達式元素都是有相應的數學意義的，比如運算符有優先級，需要的運算數個數，以及最重要的計算函數指針這些屬性，而運算數最主要的屬性就是它所對應的數值了。比如表達式 1-2*(sin(pi/3))^2 在經過詞法分析以后將被分割成如下的表達式元素序列：

???????????????????????? ? ? ? ? ? ? ? ?? ? 1? -? 2? *? (? sin? (? pi? /? 3? )? )? ^? 2

???? 其中的各個部件都已經有了數學意義（這需要相應的表達式部件類的實現），比如運算符 * 具有屬性： 字符串體：“*”，優先級：2， 所需運算數個數：2， 計算函數指針：（一個完成乘法運算的函數）。而最后的運算數2具有屬性：字符串體：“2”，數值：2.

????? 這里有一個非常重要的設計，就是把數學函數當成運算符處理。這樣做的理由是，函數運算符跟普通的四則混合運算符都能對給定的若干個實數，計算出一個結果來，這說明它們在本質上是一致的，你可以把加法 2+3 寫成函數調用的形式 +(2,3)，也可以把函數調用 pow(2,3) 按照二元運算符的慣例放在兩個運算數之間： 2 pow 3，想必人們對于 2^3 這樣的指數寫法習以為常，那么這個 2 pow 3 不也是一脈相承的么？而對于一元函數也是一樣，一元運算符負號放在運算符之前，那么 sin(3) 也可以寫成 sin 3 的形式。總之，把函數運算符跟普通運算符統一處理，這是 abacus 在設計上的一大特色。

????? 接下來就要調整表達式的結構，傳統的數學表達式其實是很不規范的，歷史上加減乘除這些二元運算符最早發明，很自然的就把它們放在兩個運算符之間了，但同樣的形式對于非二元運算符就不適用了。又如，作為一元運算符的負號是放在運算數之前的，而階乘符號卻是放在運算數之后的，而函數運算符卻采用了另外一種寫法： opt(a1,a2,.....)。由此可見傳統的數學表達式雖然對人來說是易于理解的，但卻不利于計算機進行處理，在此我們需要用一種統一的觀點來看待所有的運算符，即運算符的本質是一個映射，能對給定的若個數（輸入）產生一個確定的結果（輸出），有了這一點認識，我們就希望用一種統一的形式來刻畫表達式。

????? 我們采用“運算符前置”的形式來規范數學表達式的結構，它把任何一個表達式放在一對小括號內部，而小括號內的第一個對象就是運算符，剩余的對象均是參與運算的運算數，例如 2+3 的規范形式為 (+ 2 3)，而 sin(pi) 的規范式為 (sin pi)，并且表達式可以任意嵌套，比如 5*(2-3) 的規范形式為 (* 5 (- 2 3))，作為一個更復雜的例子，一元二次方程x^2-3x+2=0的求根公式（正根）將表示為 (/ (+ (- (-3)) (sqrt (- ((^ (- 3) 2)) (* (* 4 1) 2)))) (* 2 1)) 。雖然這樣的表達式對于人來講是一種痛苦，但由于其格式的規范性，計算機是樂于處理這樣的結構的。

????? 由傳統形式向規范式轉換的過程我們就稱之為語法分析，如果有語法錯誤，在這個過程中將會被發現。在語法分析之前也應該會有一些預處理，例如在詞法分析階段并不能區分負號與減號，這需要在語法分析之前進行一點“有語法傾向”的檢查糾正，然后根據括號的層次提升運算符的優先級。

???? 表達式在經過語法分析之后，就已經被轉換為規范式了，這個時候進行計算就相當簡單了，只要采用遞歸的方式，在表達式中查找主運算符（即優先級最低的運算符），然后檢查剩余的各個運算對象，如果某個運算對象本身也是一個表達式，即含有子表達式，則先計算子表達式的值，最后計算整個表達式的值。 1-2*(sin(pi/3))^2 的計算過程如下：

轉換為規范式：? (- 1 (* 2 (^ (sin (/ pi 3)) 2)))

計算過程：

????? Step 1:???? (- 1 (* 2 (^ (sin (/ pi 3)) 2)))

????? Step2:???? (- 1 (* 2 (^ (sin 1.047197551) 2)))

????? Step3:???? (- 1 (* 2 (^ 0.8660256282 2)))

????? Step4:???? (- 1 (* 2 0.7500010327))

????? Step5:???? (- 1 1.500002065)

????? Step6:???? -0.500002065

這樣就完成了計算過程。在此處可以看到這個“規范式”帶來的一個最大的好處：把語法分析跟遞歸計算分離開來了，如果不轉換成這種規范式而使用傳統的數學表達式，那么由于表達式的各種形式（分一元普通運算符，二元普通運算符，函數運算符.....），就只能在語法分析的過程中根據相應的運算符選擇合適的形式來進行計算了。而現在引入了這種規范式，在計算過程中根本不用去關心這個運算符是什么類型的運算符。這說明，運算符前置表達式的引進，是 abacus 的另一個非常好的設計。

????? 至此大體設計基本上就完成了。這里有一個用腦圖描述的計算器 abacus 的實現，一看就懂的：

http://www.mindomo.com/mindmap/abacus-5b6804e0f3fa466f96bc198c9b5d63d3

zhcosin

2012-10-29

?????

???

轉載于:https://my.oschina.net/zhcosin/blog/86083

總結

以上是生活随笔為你收集整理的计算器 abacus 技术文档之二----初步设计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。