出一個典型的算術(shù)題： (6+2*5)/4
從題中，我們首先算 2*5=10 接下來算 6+10=16 最后算 16/4 =4 所以，結(jié)果是4
計(jì)算機(jī)怎么算？還好前輩給我們列出來一堆的算法，我們隨便選一個就可以了。
第一種算法
使用棧來解決，意思就是把不優(yōu)極最低的壓到棧的最下面去，按照先進(jìn)后出的原則，那么最優(yōu)先級最低的就是最后計(jì)算了。
計(jì)算過程：
我們建立兩個棧，一個是數(shù)據(jù)棧，一個是計(jì)算符號棧，以(6+2*5)/4為例子，看看倒底是怎么計(jì)算的。
假設(shè)：
1)優(yōu)先級
符號之間的優(yōu)先級如下：
“(“ “)” -1
“+”,”-” 0
“*”,”/” 1
數(shù)值越大，則越優(yōu)先，同級別的比較時(shí) 先出現(xiàn)的優(yōu)先。
2）將”(”,”)”設(shè)為特殊運(yùn)算符，即單目運(yùn)算，兩鄰兩個運(yùn)算符則可對消。
3) 計(jì)算條件
(1) 當(dāng)前運(yùn)算符不等于“”（特殊結(jié)束符）
(2) 運(yùn)算符棧里的運(yùn)行算個數(shù)>=1時(shí)
(3) 出棧口的運(yùn)算符優(yōu)先級高于將要入棧的運(yùn)算符時(shí)或者兩者可對消時(shí)。
計(jì)算時(shí)，則將符號出棧參與計(jì)算，數(shù)值棧的出棧口前兩位元素出棧參與計(jì)算，計(jì)算結(jié)果值向數(shù)值棧壓棧，并進(jìn)行遞歸此操作。
 圖1： |
1) “(” 壓入符號棧 2 ) “6”壓入數(shù)值棧
3) “（”與”+”比較優(yōu)先級，認(rèn)為”（”比”+”優(yōu)先級低，則不滿足計(jì)算條件，將”+”壓入符號棧.
 圖2： |
1) 將”2” 壓入數(shù)值棧。
2) 將”*”與”+”比較優(yōu)先級，算得”+”優(yōu)先級低于”*”，則不滿足計(jì)算條件，將”*”壓入符號棧。
 圖3： |
1) 將 “5”壓入數(shù)植棧。 2) 將“*“與”)”比較優(yōu)先級，得出”*”比”)”優(yōu)先級要高。進(jìn)行計(jì)算，將”*”出棧、”5”、”2”出棧，參與計(jì)算
 圖4： |
1) 將 2*5 =10的結(jié)果壓入數(shù)值棧。
2) （遞歸）比較 “+”與”)”優(yōu)先級，得出”+”比”)”優(yōu)先級要高。再進(jìn)行計(jì)算，將”+”出棧、”10”、”6”出棧，參與計(jì)算。
 圖 5： |
1) 將 6+10 =16的結(jié)果壓入數(shù)值棧。
2) （遞歸）比較 “)”與”(”優(yōu)先級，得出兩者可以對消，將”(”符號出棧，與”)”對消，繼續(xù)取下一個符號。
 圖6： |
1) 將”/”入符號棧。
2）將”4”入數(shù)值棧。
3) 發(fā)現(xiàn)””算式結(jié)束符，則進(jìn)行計(jì)算, 將 “/”、”4’、”16”出棧，參與計(jì)算。
 圖7： |
1) 將計(jì)算結(jié)果壓入數(shù)值棧。
成功了! 辛苦的計(jì)算工作終于干完了，看起來比人腦計(jì)算復(fù)雜多了：）
第二種算法
第二種方法，我們簡單的提一下，在這里不作詳細(xì)過程的敘述。第二種，就是使用樹的方式，將一個算式組織成一定規(guī)律的樹，之后，再進(jìn)行遍歷計(jì)算即得得到結(jié)果。還是以上面的算式作例子，最終形成的樹的樣式：（注意“()”這個符號要特殊處理）
 圖8： |
使用樹的深度遍歷即可算出最終的結(jié)果。
程序?qū)崿F(xiàn)
本文，給出使用棧處理四則運(yùn)算的C#實(shí)現(xiàn)方法，如下：
| CalUtility.cs using System; namespace Calculate { /// <summary> /// CalUtility 的摘要說明。 /// 讀算式輔助工具 /// </summary> public class CalUtility { System.Text.StringBuilder StrB; private int iCurr=0; private int iCount=0; /// <summary> /// 構(gòu)造方法 /// </summary> public CalUtility(string calStr) { StrB = new System.Text.StringBuilder(calStr.Trim()); iCount = System.Text.Encoding.Default.GetByteCount(calStr.Trim()); } /// <summary> /// 取段，自動分析數(shù)值或計(jì)算符 /// </summary> /// <returns></returns> public string getItem() { //結(jié)束了 if(iCurr==iCount) return ""; char ChTmp = StrB[iCurr]; bool b=IsNum(ChTmp); if(!b) { iCurr++; return ChTmp.ToString(); } string strTmp=""; while(IsNum(ChTmp)==b && iCurr<iCount) { ChTmp = StrB[iCurr]; if(IsNum(ChTmp)==b) strTmp +=ChTmp; else break; iCurr++; } return strTmp; } /// <summary> /// 是否是數(shù)字 /// </summary> /// <param name="c">內(nèi)容</param> /// <returns></returns> public bool IsNum(char c) { if((c>=’0’ && c<=’9’)|| c==’.’) { return true; } else { return false; } } /// <summary> /// 是否是數(shù)字 /// </summary> /// <param name="c">內(nèi)容</param> /// <returns></returns> public bool IsNum(string c) { if(c.Equals("")) return false; if((c[0]>=’0’ && c[0]<=’9’)|| c[0]==’.’) { return true; } else { return false; } } /// <summary> /// 比較str1和str2兩個運(yùn)算符的優(yōu)先級，ture表示str1高于str2，false表示str1低于str2 /// </summary> /// <param name="str1">計(jì)算符1</param> /// <param name="str2">計(jì)算符2</param> /// <returns></returns> public bool Compare(string str1,string str2) { return getPriority(str1)>=getPriority(str2); } /// <summary> /// 取得計(jì)算符號的優(yōu)先級 /// </summary> /// <param name="str">計(jì)算符</param> /// <returns></returns> public int getPriority(string str) { if(str.Equals("")) { return -1; } if(str.Equals("(")) { return 0; } if(str.Equals("+")||str.Equals("-")) { return 1; } if(str.Equals("*")||str.Equals("/")) { return 2; } if(str.Equals(")")) { return 0; } return 0; } } } IOper.cs using System; namespace Calculate { /// <summary> /// IOper 的摘要說明。 /// 計(jì)算符接口 /// </summary> public interface IOper { /// <summary> /// 計(jì)算符計(jì)算接口計(jì)算方法 /// </summary> /// <param name="o1">參數(shù)1</param> /// <param name="o2">參數(shù)2</param> /// <returns></returns> object Oper(object o1,object o2); } } Opers.cs using System; namespace Calculate { /// <summary> /// Opers 的摘要說明。 /// 各類計(jì)算符的接口實(shí)現(xiàn)，加減乘除 /// </summary> public class OperAdd:IOper { public OperAdd() { // // TODO: 在此處添加構(gòu)造函數(shù)邏輯 // } #region IOper 成員 public object Oper(object o1, object o2) { Decimal d1 = Decimal.Parse(o1.ToString()); Decimal d2 = Decimal.Parse(o2.ToString()); return d1+d2; } #endregion } public class OperDec:IOper { public OperDec() { // // TODO: 在此處添加構(gòu)造函數(shù)邏輯 // } #region IOper 成員 public object Oper(object o1, object o2) { Decimal d1 = Decimal.Parse(o1.ToString()); Decimal d2 = Decimal.Parse(o2.ToString()); return d1-d2; } #endregion } public class OperRide:IOper { public OperRide() { // // TODO: 在此處添加構(gòu)造函數(shù)邏輯 // } #region IOper 成員 public object Oper(object o1, object o2) { Decimal d1 = Decimal.Parse(o1.ToString()); Decimal d2 = Decimal.Parse(o2.ToString()); return d1*d2; } #endregion } public class OperDiv:IOper { public OperDiv() { // // TODO: 在此處添加構(gòu)造函數(shù)邏輯 // } #region IOper 成員 public object Oper(object o1, object o2) { Decimal d1 = Decimal.Parse(o1.ToString()); Decimal d2 = Decimal.Parse(o2.ToString()); return d1/d2; } #endregion } } OperFactory.cs using System; namespace Calculate { /// <summary> /// OperFactory 的摘要說明。 /// 計(jì)算符接口工廠 /// </summary> public class OperFactory { public OperFactory() { } public IOper CreateOper(string Oper) { if(Oper.Equals("+")) { IOper p = new OperAdd(); return p; } if(Oper.Equals("-")) { IOper p = new OperDec(); return p; } if(Oper.Equals("*")) { IOper p = new OperRide(); return p; } if(Oper.Equals("/")) { IOper p = new OperDiv(); return p; } return null; } } } Calculate.cs using System; using System.Collections; namespace Calculate { /// <summary> /// Calculate 的摘要說明。 /// 計(jì)算實(shí)現(xiàn)主類 /// </summary> public class Calculate { /// <summary> /// 算術(shù)符棧 /// </summary> private ArrayList HList; /// <summary> /// 數(shù)值棧 /// </summary> public ArrayList Vlist; /// <summary> /// 讀算試工具 /// </summary> private CalUtility cu; /// <summary> /// 運(yùn)算操作器工廠 /// </summary> private OperFactory of; /// <summary> /// 構(gòu)造方法 /// </summary> /// <param name="str">算式</param> public Calculate(string str) { // // TODO: 在此處添加構(gòu)造函數(shù)邏輯 // HList = new ArrayList(); Vlist = new ArrayList(); of = new OperFactory(); cu = new CalUtility(str); } /// <summary> /// 開始計(jì)算 /// </summary> public object DoCal() { string strTmp=cu.getItem(); while(true) { if(cu.IsNum(strTmp)) { //如果是數(shù)值，則寫入數(shù)據(jù)棧 Vlist.Add(strTmp); } else { //數(shù)值 Cal(strTmp); } if(strTmp.Equals("")) break; strTmp=cu.getItem(); } return Vlist[0]; } /// <summary> /// 計(jì)算 /// </summary> /// <param name="str">計(jì)算符</param> private void Cal(string str) { //符號表為空，而且當(dāng)前符號為""，則認(rèn)為已經(jīng)計(jì)算完畢 if(str.Equals("")&&HList.Count==0) return; if(HList.Count>0) { //符號是否可以對消？ if(HList[HList.Count-1].ToString().Equals("(") && str.Equals(")")) { HList.RemoveAt(HList.Count-1); if(HList.Count>0) { str=HList[HList.Count-1].ToString(); HList.RemoveAt(HList.Count-1); Cal(str); } return; } //比較優(yōu)先級 if(cu.Compare(HList[HList.Count-1].ToString(),str)) { //如果優(yōu)先，則計(jì)算 IOper p = of.CreateOper(HList[HList.Count -1].ToString()); if(p!=null) { Vlist[Vlist.Count -2] = p.Oper(Vlist[Vlist.Count-2],Vlist[Vlist.Count-1]); HList.RemoveAt(HList.Count -1); Vlist.RemoveAt(Vlist.Count -1); Cal(str); } return; } if(!str.Equals("")) HList.Add(str); } else { if(!str.Equals("")) HList.Add(str); } } } } |
后記
使用這種方法，我們可以完成更復(fù)雜的混合運(yùn)算，比如說：可以支持函數(shù)運(yùn)算的混合運(yùn)算，更進(jìn)一步，可以支持自定義函數(shù)的混合運(yùn)算，最終可以將這種算法運(yùn)用在自定義報(bào)表、工資處理等等應(yīng)用領(lǐng)域，很希望有相關(guān)興趣的朋友與我交流。
