對于計算器，有很多成熟的理論。本文章討論的是利用一個操作數(shù)堆棧和一個運算符堆棧進行運算的方法。這種算法已經(jīng)有很完善的解決方案，此處討論的是最簡化
的模型，旨在讓初學者在最短的時間內(nèi)學到此算法的精髓，并能靈活的應用到科研的任何一個領(lǐng)域。
簡單表達式的計算
首先請看這個表達式：
3＋5＋6＊7＊8＾2＾3 （8＾2指的是82）
這里運算有三種優(yōu)先級“＾”--＞
“＊”--＞“＋”， 如何實現(xiàn)優(yōu)先級運算呢？
當掃描字符串3＋5＋6＊7＊8＾2＾3的時候。
1. 先移進3＋5，發(fā)現(xiàn)下一個運算符是＋，優(yōu)先級與上一個相同，于是就先計算3＋5，將它們改為8。于是式子變?yōu)椋?＋6＊7＊8＾2＾3
2. 現(xiàn)在下一運算符＊優(yōu)先級比上一個＋要高，于是繼續(xù)前移：8＋6＊7＊8＾2＾3
3. 現(xiàn)在下一個運算符是＊，與上一個相同，于是先計算6＊7，式子變?yōu)椋?＋42＊8＾2＾3
4. 繼續(xù)：8＋42＊8＾2＾3
5. 8＋42＊64＾3
6. 8＋42＊262144
7. 8＋1．101＊107
8. 1．101＊107
現(xiàn)在式子變成一個數(shù)，整個運算也就結(jié)束了。
但怎樣在計算機中完成這個過程呢？當遇到8＋6＊7時必須先運算6＊7，但這時8和＋保存在哪里呢？這里使用的方法是：建立一個操作數(shù)堆棧和一個運算符堆棧，把8和＋分別壓到兩個堆棧中。
對于式子：3＋5＋6＊7-8＾2
剩余式子 操作數(shù)堆棧 運算符堆棧 優(yōu)先級比較 操作
3＋5＋6＊7-8＾2
±6＊7
-8＾2
3，5
±
相等 計算 3＋5＝8
＋6＊7-8＾2 8
＊7
-8＾2
8，6
±
大于
-8＾2
8，6，7
＋，＊
小于 計算6＊7＝42
-8＾2
8，42
＋
等于 計算 8＋42＝50
-8＾2 50
＾2
50，8
-
大于
50，8，2
-，＾
計算8＾2＝64
50，64
-
計算 50-64＝-14
-14
＾
--------------------------------------------------------------------------------------------------------------
可以看出，如果利用操作數(shù)堆棧和運算符堆棧的話，只要：
1． 步進掃描表達式。
2． 遇到操作數(shù)就壓入操作數(shù)堆棧中，遇到運算符就將它的優(yōu)先級與運算符堆棧棧頂運算符的優(yōu)先級比較，如果它的優(yōu)先級更大，就將它壓入堆棧，否則就將棧頂運算符彈出來進行運算。
只要這樣就可以實現(xiàn)優(yōu)先級的運算。
優(yōu)先級的改變
在我的示例程序中規(guī)定了3種優(yōu)先級
＋、-、自反運算（-x，-y，-z，-1，-2） ：優(yōu)先級為
1（較低）
＊、／?。簝?yōu)先級為2
＾ ：優(yōu)先級為3（最高）
但“（”的優(yōu)先級應該是多少，括號指的是開始一個新的運算，對于3＋5＊（6-2），當掃描到“（”時，原先的
優(yōu)先級就全部失效了，一切需要重新計算，因此掃描時遇到“（”，就將它無條件壓入棧中，同時置最低優(yōu)先級-
1。與此操作相同的還有 “sin（”、“cos（”、“tan（”、“tg（”、“lg（”、“ln（”等.
遇到“）”，就應該不停出棧運算直至找到“（”、“sin（”、“cos（”、“tan（”、“tg（”、“lg（”、“ln（”等。
程序流程
對于一個合法的簡單數(shù)學表達式，肯定是一個操作數(shù)跟著一個運算符，第一個和最后一個都是操作數(shù)。因此最簡單的程序編寫方法就是寫一個取操作數(shù)的程序
CCalc：：GetOperand（），再寫一個取運算符的程序CCalc：：GetOperator（），然后循環(huán)執(zhí)行。
while(!GetOperand()&&!GetOperator()&&!vError);
這樣就可以計算出最終的結(jié)果。
1． 取操作數(shù)GetOperand（）：
（1）取操作數(shù)時首先遇到的不一定就是操作數(shù)本身，而可能是“（”、“sin（”、“cos（”、“tan（”、“tg（”、“lg（”、“ln（”或自反運算符“-”或無意義的“＋”號，首先將它們壓入運算符棧中。
（2）然后檢查是不是“x”、“y”、“z”等變量或“PI”等常量，有的話將它們的值壓到操作數(shù)棧中。
（3）如果不是變量或常量，則檢查數(shù)的合法性，如果不是合法數(shù)，就退出全部運算。
2．取運算符GetOperator（）：
（1）取運算符時首先遇到的不一定就是運算符，而可能是“）”，先要對它進行處理。
（2）然后檢查是不是掃描到了最后，如果是就清棧輸出結(jié)果。
（3）取出新運算符并給它對應的優(yōu)先級。
（4）如果運算符堆棧不為空，從中彈出一個運算符，比較優(yōu)先級，如果新的運算符優(yōu)先級小于等于彈出運算符優(yōu)先級，就把彈出運算符重新壓回去，否則對彈出運算符進行運算。
（5）將新運算符壓入堆棧中。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=284095
