我們拿到一個(gè)字符串比如：20+31*(100+1)的時(shí)候用口算就能算出結(jié)果為3151，因?yàn)檫@是中綴表達(dá)式對(duì)于人類的思維很簡(jiǎn)單，但是對(duì)于計(jì)算機(jī)就比較復(fù)雜了。相對(duì)的后綴表達(dá)式適合計(jì)算機(jī)進(jìn)行計(jì)算。

我們就從簡(jiǎn)單到復(fù)雜，逐步實(shí)現(xiàn)對(duì)公式的解析(下述的代碼沒有經(jīng)過(guò)嚴(yán)格驗(yàn)證，可能會(huì)存在極端情況的BUG，作為一種思路僅供參考，商用環(huán)境還需細(xì)細(xì)修改)。

實(shí)現(xiàn)簡(jiǎn)單的數(shù)字的加減乘除

我們從實(shí)現(xiàn)簡(jiǎn)單的數(shù)字的加減乘除開始主要是提供一個(gè)思路有需要可以自己修改擴(kuò)展比如增加函數(shù)、字符串、數(shù)組等（推薦一個(gè)項(xiàng)目寫的感覺就不錯(cuò)https://github.com/KovtunV/NoStringEvaluating），那么我們只需要關(guān)注加減乘除等操作符、左右括號(hào)和操作數(shù)(整數(shù)、小數(shù)和負(fù)數(shù))，所以我們先建立三個(gè)枚舉類BracketEnum、NodeTypeEnum和OperatorEnum如下：

BracketEnum是括號(hào)枚舉，也就是左右括號(hào)"()"

?View Code

NodeTypeEnum是節(jié)點(diǎn)類型枚舉，就簡(jiǎn)單分為操作符、操作數(shù)和括號(hào)

?View Code

OperatorEnum是操作符枚舉，主要就是加減乘除這些簡(jiǎn)單的

?View Code

然后我們需要做以下三步：

1. 解析公式將字符轉(zhuǎn)化為便于操作的節(jié)點(diǎn)信息

2. 進(jìn)行解析為后綴表達(dá)式

3. 進(jìn)行計(jì)算

?1、解析公式轉(zhuǎn)為節(jié)點(diǎn)信息

根據(jù)我們的NodeTypeEnum節(jié)點(diǎn)類型枚舉我們需要三個(gè)不同的節(jié)點(diǎn)信息類方便我們的操作，我們先創(chuàng)建基類BaseNode以后的節(jié)點(diǎn)類都繼承它

public class BaseNode ? ?{ ? ? ? ?public BaseNode(NodeTypeEnum nodeType) ? ? ? ?{ ? ? ? ? ? ?NodeType = nodeType; ? ? ? ?} ? ? ? ?/// <summary> ? ? ? ?/// 節(jié)點(diǎn)類型 ? ? ? ?/// </summary> ? ? ? ?public NodeTypeEnum NodeType { get; set; } ? ?}

?然后我們分別創(chuàng)建BracketNode、NumberNode和OperatorNode類，分別是括號(hào)節(jié)點(diǎn)信息、操作數(shù)節(jié)點(diǎn)新和操作符節(jié)點(diǎn)信息，它們各有自己的具體實(shí)現(xiàn)，如下：

?View Code

?View Code

?View Code

?有了節(jié)點(diǎn)信息類，那我們肯定還要有對(duì)應(yīng)的解析類分別是BracketReader(括號(hào)解析)、NumberReader(操作數(shù)解析)和OperatorReader(操作符解析)，解析類就是為了將公式字符串解析為對(duì)應(yīng)的節(jié)點(diǎn)信息具體如下：

?View Code

?View Code

?View Code

有了以上的準(zhǔn)備，我們就可以將公式轉(zhuǎn)為我們的節(jié)點(diǎn)信息了如下

? ? ? ?/// <summary> ? ? ? ?/// 解析公式為節(jié)點(diǎn) ? ? ? ?/// </summary> ? ? ? ?/// <param name="formula">公式字符串</param> ? ? ? ?/// <returns></returns> ? ? ? ?public static List<BaseNode> AnalysisFormulaToNodes(string formula) ? ? ? ?{ ? ? ? ? ? ?var nodes = new List<BaseNode>(); ? ? ? ? ? ?for(var index = 0;index< formula.Length; index++) ? ? ? ? ? ?{ ? ? ? ? ? ? ? ?if (NumberReader.TryProceedNumber(nodes, formula.AsSpan(), ref index)) ? ? ? ? ? ? ? ? ? ?continue; ? ? ? ? ? ? ? ?if (OperatorReader.TryProceedOperator(nodes, formula.AsSpan(), ref index)) ? ? ? ? ? ? ? ? ? ?continue; ? ? ? ? ? ? ? ?if (BracketReader.TryProceedOpenBracket(nodes, formula.AsSpan(), ref index)) ? ? ? ? ? ? ? ? ? ?continue; ? ? ? ? ? ? ? ?if (BracketReader.TryProceedCloseBracket(nodes, formula.AsSpan(), ref index)) ? ? ? ? ? ? ? ? ? ?continue; ? ? ? ? ? ?} ? ? ? ? ? ?return nodes; ? ? ? ?}

?2、轉(zhuǎn)為后綴表達(dá)式

轉(zhuǎn)為后綴表達(dá)式需要執(zhí)行以下條件：

首先需要分配2個(gè)棧，一個(gè)作為臨時(shí)存儲(chǔ)運(yùn)算符的棧S1（含一個(gè)結(jié)束符號(hào)），一個(gè)作為存放結(jié)果（逆波蘭式）的棧S2（空棧），S1棧可先放入優(yōu)先級(jí)最低的運(yùn)算符#，注意，中綴式應(yīng)以此最低優(yōu)先級(jí)的運(yùn)算符結(jié)束?？芍付ㄆ渌址?，不一定非#不可。從中綴式的左端開始取字符，逐序進(jìn)行如下步驟：

（1）若取出的字符是操作數(shù)，則分析出完整的運(yùn)算數(shù)，該操作數(shù)直接送入S2棧。

（2）若取出的字符是運(yùn)算符，則將該運(yùn)算符與S1棧棧頂元素比較，如果該運(yùn)算符(不包括括號(hào)運(yùn)算符)優(yōu)先級(jí)高于S1棧棧頂運(yùn)算符（包括左括號(hào)）優(yōu)先級(jí)，則將該運(yùn)算符進(jìn)S1棧，否則，將S1棧的棧頂運(yùn)算符彈出，送入S2棧中，直至S1棧棧頂運(yùn)算符（包括左括號(hào)）低于（不包括等于）該運(yùn)算符優(yōu)先級(jí)時(shí)停止彈出運(yùn)算符，最后將該運(yùn)算符送入S1棧。

（3）若取出的字符是“（”，則直接送入S1棧頂。

（4）若取出的字符是“）”，則將距離S1棧棧頂最近的“（”之間的運(yùn)算符，逐個(gè)出棧，依次送入S2棧，此時(shí)拋棄“（”。

（5）重復(fù)上面的1~4步，直至處理完所有的輸入字符。

（6）若取出的字符是“#”，則將S1棧內(nèi)所有運(yùn)算符（不包括“#”），逐個(gè)出棧，依次送入S2棧。

具體實(shí)現(xiàn)代碼如下：

?View Code

3、計(jì)算后綴表達(dá)式

以(a+b)*c為例子進(jìn)行說(shuō)明：

(a+b)*c的逆波蘭式為ab+c*，假設(shè)計(jì)算機(jī)把a(bǔ)b+c*按從左到右的順序壓入棧中，并且按照遇到運(yùn)算符就把棧頂兩個(gè)元素出棧，執(zhí)行運(yùn)算，得到的結(jié)果再入棧的原則來(lái)進(jìn)行處理，那么ab+c*的執(zhí)行結(jié)果如下：

1）a入棧（0位置）

2）b入棧（1位置）

3）遇到運(yùn)算符“+”，將a和b出棧，執(zhí)行a+b的操作，得到結(jié)果d=a+b，再將d入棧（0位置）

4）c入棧（1位置）

5）遇到運(yùn)算符“*”，將d和c出棧，執(zhí)行d*c的操作，得到結(jié)果e，再將e入棧（0位置）

經(jīng)過(guò)以上運(yùn)算，計(jì)算機(jī)就可以得到(a+b)*c的運(yùn)算結(jié)果e了。

具體實(shí)現(xiàn)代碼如下：

? ? ? ?/// <summary> ? ? ? ?/// 計(jì)算后綴表達(dá)式 ? ? ? ?/// </summary> ? ? ? ?/// <param name="nodes"></param> ? ? ? ?/// <returns></returns> ? ? ? ?public static double CalculationRPN(List<BaseNode> nodes) ? ? ? ?{ ? ? ? ? ? ?double result = 0; ? ? ? ? ? ?Stack<BaseNode> stack = new Stack<BaseNode>(); ? ? ? ? ? ?foreach(var t in nodes) ? ? ? ? ? ?{ ? ? ? ? ? ? ? ?if(t.NodeType == NodeTypeEnum.Number) ? ? ? ? ? ? ? ?{ ? ? ? ? ? ? ? ? ? ?//操作數(shù)直接入棧 ? ? ? ? ? ? ? ? ? ?stack.Push(t); ? ? ? ? ? ? ? ?} ? ? ? ? ? ? ? ?else if(t.NodeType == NodeTypeEnum.Operator) ? ? ? ? ? ? ? ?{ ? ? ? ? ? ? ? ? ? ?//操作符彈出棧頂兩個(gè)進(jìn)行計(jì)算 ? ? ? ? ? ? ? ? ? ?var a = stack.Pop(); ? ? ? ? ? ? ? ? ? ?var b = stack.Pop(); ? ? ? ? ? ? ? ? ? ?var operate = t as OperatorNode; ? ? ? ? ? ? ? ? ? ?var value = operate.OperatorKey switch ? ? ? ? ? ? ? ? ? ?{ ? ? ? ? ? ? ? ? ? ? ? ?// 數(shù)學(xué)操作符 ? ? ? ? ? ? ? ? ? ? ? ?OperatorEnum.Multiply => OperatorService.Multiply(a, b), ? ? ? ? ? ? ? ? ? ? ? ?OperatorEnum.Divide => OperatorService.Divide(a, b), ? ? ? ? ? ? ? ? ? ? ? ?OperatorEnum.Plus => OperatorService.Plus(a, b), ? ? ? ? ? ? ? ? ? ? ? ?OperatorEnum.Minus => OperatorService.Minus(a, b), ? ? ? ? ? ? ? ? ? ? ? ?OperatorEnum.Power => OperatorService.Power(a, b), ? ? ? ? ? ? ? ? ? ?}; ? ? ? ? ? ? ? ? ? ?stack.Push(new NumberNode(value)); ? ? ? ? ? ? ? ?} ? ? ? ? ? ?} ? ? ? ? ? ?result = (stack.Pop() as NumberNode).Number; ? ? ? ? ? ?return result; ? ? ? ?}

數(shù)學(xué)操作符執(zhí)行代碼如下主要為了進(jìn)行加減乘除簡(jiǎn)單的計(jì)算：

?View Code

最后串在一起就能得到結(jié)果啦，就像下面這樣

? ? ? ?/// <summary> ? ? ? ?/// 計(jì)算 ? ? ? ?/// </summary> ? ? ? ?/// <param name="formula">公式字符串</param> ? ? ? ?/// <returns></returns> ? ? ? ?public static double Calculation(string formula) ? ? ? ?{ ? ? ? ? ? ?//1、獲取公式節(jié)點(diǎn) ? ? ? ? ? ?var nodes = AnalysisFormulaToNodes(formula); ? ? ? ? ? ?//2、轉(zhuǎn)后綴表達(dá)式 ? ? ? ? ? ?var rpnNodes = GetRPN(nodes); ? ? ? ? ? ?//3、計(jì)算對(duì)后綴表達(dá)式求值 ? ? ? ? ? ?var result = CalculationRPN(rpnNodes); ? ? ? ? ? ?return result; ? ? ? ?}