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