C#利用后綴表達(dá)式解析計(jì)算字符串公式
當(dāng)我們拿到一個(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ì)公式的解析(下述的代碼沒(méi)有經(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ù)字的加減乘除開(kāi)始主要是提供一個(gè)思路有需要可以自己修改擴(kuò)展比如增加函數(shù)、字符串、數(shù)組等(推薦一個(gè)項(xiàng)目寫(xiě)的感覺(jué)就不錯(cuò)https://github.com/KovtunV/NoStringEvaluating),那么我們只需要關(guān)注加減乘除等操作符、左右括號(hào)和操作數(shù)(整數(shù)、小數(shù)和負(fù)數(shù)),所以我們先建立三個(gè)枚舉類BracketEnum
、NodeTypeEnum
和OperatorEnum
如下:
BracketEnum
是括號(hào)枚舉,也就是左右括號(hào)"()"
public enum BracketEnum { /// <summary> /// Undefined /// </summary> Undefined = 0, /// <summary> /// 左括號(hào) /// </summary> Open, /// <summary> /// 右括號(hào) /// </summary> Close }
NodeTypeEnum
是節(jié)點(diǎn)類型枚舉,就簡(jiǎn)單分為操作符、操作數(shù)和括號(hào)
public enum NodeTypeEnum { /// <summary> /// Null /// </summary> Null = 0, /// <summary> /// 操作數(shù) /// </summary> Number, /// <summary> /// 操作符 /// </summary> Operator, /// <summary> /// 括號(hào) /// </summary> Bracket, }
OperatorEnum
是操作符枚舉,主要就是加減乘除這些簡(jiǎn)單的
public enum OperatorEnum { /// <summary> /// Undefined /// </summary> Undefined = 0, /// <summary> /// + /// </summary> Plus, /// <summary> /// - /// </summary> Minus, /// <summary> /// * /// </summary> Multiply, /// <summary> /// / /// </summary> Divide, /// <summary> /// ^ /// </summary> Power, }
然后我們需要做以下三步:
- 解析公式將字符轉(zhuǎn)化為便于操作的節(jié)點(diǎn)信息
- 進(jìn)行解析為后綴表達(dá)式
- 進(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),如下:
public class BracketNode : BaseNode { /// <summary> /// 括號(hào)值 /// </summary> public BracketEnum Bracket { get; } /// <summary> /// 公式括號(hào)節(jié)點(diǎn) /// </summary> public BracketNode(BracketEnum bracket) : base(NodeTypeEnum.Bracket) { Bracket = bracket; } }
public class NumberNode : BaseNode { /// <summary> /// 數(shù)字值 /// </summary> public double Number { get; } public NumberNode(double number) : base(NodeTypeEnum.Number) { Number = number; } }
public class OperatorNode : BaseNode { /// <summary> /// 操作字符串枚舉 /// </summary> public OperatorEnum OperatorKey { get; } /// <summary> /// 優(yōu)先級(jí) /// </summary> public int Priority { get; } public OperatorNode(OperatorEnum operatorKey) : base(NodeTypeEnum.Operator) { OperatorKey = operatorKey; Priority = GetPriority(); } private int GetPriority() { var priority = OperatorKey switch { OperatorEnum.Power => 6, OperatorEnum.Multiply => 5, OperatorEnum.Divide => 5, OperatorEnum.Plus => 4, OperatorEnum.Minus => 4, _ => 0 }; return priority; } }
有了節(jié)點(diǎn)信息類,那我們肯定還要有對(duì)應(yīng)的解析類分別是BracketReader(括號(hào)解析)
、NumberReader(操作數(shù)解析)
和OperatorReader(操作符解析)
,解析類就是為了將公式字符串解析為對(duì)應(yīng)的節(jié)點(diǎn)信息具體如下:
public static class BracketReader { /// <summary> /// 左右括號(hào)字符 /// </summary> private const char OPEN_BRACKET_CHAR = '('; private const char CLOSE_BRACKET_CHAR = ')'; /// <summary> /// 嘗試獲取左括號(hào) /// </summary> /// <param name="nodes">公式節(jié)點(diǎn)信息</param> /// <param name="formula">公式字符</param> /// <param name="index">公式讀取的下標(biāo)</param> /// <returns></returns> public static bool TryProceedOpenBracket(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref int index) { if (formula[index].Equals(OPEN_BRACKET_CHAR)) { nodes.Add(new BracketNode(BracketEnum.Open)); return true; } return false; } /// <summary> /// 嘗試獲取右括號(hào) /// </summary> /// <param name="nodes">公式節(jié)點(diǎn)信息</param> /// <param name="formula">公式字符</param> /// <param name="index">公式讀取的下標(biāo)</param> /// <returns></returns> public static bool TryProceedCloseBracket(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref int index) { if (formula[index].Equals(CLOSE_BRACKET_CHAR)) { nodes.Add(new BracketNode(BracketEnum.Close)); return true; } return false; } }
public static class NumberReader { /// <summary> /// 嘗試讀取數(shù)字 /// </summary> public static bool TryProceedNumber(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref int index) { double value = 0; var isTry = false;//是否轉(zhuǎn)換成功 var isNegative = formula[index] == '-';//是否是負(fù)數(shù) var localIndex = isNegative ? index + 1 : index; //循環(huán)判斷數(shù)字 for (int i = localIndex; i < formula.Length; i++) { var ch = formula[i]; var isLastChar = i + 1 == formula.Length; if (IsFloatingNumber(ch)) { //如果最后一個(gè)并且成功 if (isLastChar && double.TryParse(formula.Slice(index, formula.Length - index), out value)) { index = i; isTry = true; break; } } else if(double.TryParse(formula.Slice(index, i - index), out value)) { //如果不是數(shù)字比如是字母,則直接判斷之前的數(shù)字 index = i - 1; isTry = true; break; } else { break; } } if (isTry) { nodes.Add(new NumberNode(value)); } return isTry; } /// <summary> /// 判斷是不是數(shù)字或者. /// </summary> /// <param name="ch">字符</param> /// <returns></returns> private static bool IsFloatingNumber(char ch) { //是不是十進(jìn)制數(shù) var isDigit = char.IsDigit(ch); return isDigit || ch == '.'; } }
/// <summary> /// 操作符解讀 /// </summary> public static class OperatorReader { private static readonly string[] _operators = new[] { "+", "-", "*", "/", "^" }; /// <summary> /// 嘗試獲取操作符 /// </summary> public static bool TryProceedOperator(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref int index) { if (_operators.Contains(formula[index].ToString())) { nodes.Add(new OperatorNode(GetOperatorKey(formula[index].ToString()))); return true; } return false; } /// <summary> /// 獲取對(duì)應(yīng)枚舉 /// </summary> /// <param name="name"></param> /// <returns></returns> private static OperatorEnum GetOperatorKey(string name) { return name switch { "+" => OperatorEnum.Plus, "-" => OperatorEnum.Minus, "*" => OperatorEnum.Multiply, "/" => OperatorEnum.Divide, "^" => OperatorEnum.Power, _ => OperatorEnum.Undefined }; } }
有了以上的準(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é)束。可指定其他字符,不一定非#不可。從中綴式的左端開(kāi)始取字符,逐序進(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)代碼如下:
/// <summary> /// 轉(zhuǎn)為后綴表達(dá)式 /// </summary> /// <param name="nodes"></param> /// <returns></returns> public static List<BaseNode> GetRPN(List<BaseNode> nodes) { var rpnNodes = new List<BaseNode>(); var tempNodes = new Stack<BaseNode>(); foreach(var t in nodes) { //1、如果是操作數(shù)直接入棧 if(t.NodeType == NodeTypeEnum.Number) { rpnNodes.Add(t); continue; } //2、若取出的字符是運(yùn)算符,則循環(huán)比較S1棧頂?shù)倪\(yùn)算符(包括左括號(hào))優(yōu)先級(jí),如果棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)大于等于該運(yùn)算符的優(yōu)先級(jí),則S1棧頂運(yùn)算符彈出加入到S2中直至不滿足條件為止,最后將該運(yùn)算符送入S1中。 if (t.NodeType == NodeTypeEnum.Operator) { while (tempNodes.Count > 0) { var peekOperatorNode = tempNodes.Peek() as OperatorNode; if (peekOperatorNode != null && peekOperatorNode.Priority >= (t as OperatorNode).Priority) { rpnNodes.Add(tempNodes.Pop()); } else { break; } } tempNodes.Push(t); continue; } //3、若取出的字符是“(”,則直接送入S1棧頂 if(t.NodeType == NodeTypeEnum.Bracket) { if((t as BracketNode).Bracket == BracketEnum.Open) { tempNodes.Push(t); continue; } } //4、若取出的字符是“)”,則將距離S1棧棧頂最近的“(”之間的運(yùn)算符,逐個(gè)出棧,依次送入S2棧,此時(shí)拋棄“(”。 if (t.NodeType == NodeTypeEnum.Bracket) { if ((t as BracketNode).Bracket == BracketEnum.Close) { while (tempNodes.Count > 0) { var peekBracketNode = tempNodes.Peek() as BracketNode; if (tempNodes.Peek().NodeType == NodeTypeEnum.Bracket && peekBracketNode != null && peekBracketNode.Bracket == BracketEnum.Open) { break; } else { rpnNodes.Add(tempNodes.Pop()); } } tempNodes.Pop(); continue; } } //5、重復(fù)上述步驟 } if(tempNodes.Count > 0) { rpnNodes.Add(tempNodes.Pop()); } return rpnNodes; }
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ì)算:
/// <summary> /// 操作符服務(wù) /// </summary> public static class OperatorService { #region Math public static double Multiply(in BaseNode a, in BaseNode b) { var (result, _a, _b) = IsNumber(a, b); if (result) { return _a * _b; } return default; } public static double Divide(in BaseNode a, in BaseNode b) { var (result, _a, _b) = IsNumber(a, b); if (result) { return _a / _b; } return default; } public static double Plus(in BaseNode a, in BaseNode b) { var (result, _a, _b) = IsNumber(a, b); if (result) { return _a + _b; } return default; } public static double Minus(in BaseNode a, in BaseNode b) { var (result, _a, _b) = IsNumber(a, b); if (result) { return _a - _b; } return default; } public static double Power(in BaseNode a, in BaseNode b) { var (result, _a, _b) = IsNumber(a, b); if (result) { return Math.Pow(_a, _b); } return default; } /// <summary> /// 判斷是不是數(shù)字類型,并返回?cái)?shù)字 /// </summary> /// <param name="a"></param> /// <returns></returns> private static (bool,double,double) IsNumber(BaseNode a, in BaseNode b) { if(a.NodeType == NodeTypeEnum.Number && b.NodeType == NodeTypeEnum.Number) { var _a = a as NumberNode; var _b = b as NumberNode; return (true, _a.Number, _b.Number); } return (false, default, default); } #endregion }
最后串在一起就能得到結(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; }
到此這篇關(guān)于C#利用后綴表達(dá)式解析計(jì)算字符串公式的文章就介紹到這了,更多相關(guān)C#解析計(jì)算字符串公式內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c#中的浮點(diǎn)型轉(zhuǎn)整形的舍取 四舍五入和銀行家舍入實(shí)現(xiàn)代碼
c#中的浮點(diǎn)型轉(zhuǎn)整形的舍取 四舍五入和銀行家舍入實(shí)現(xiàn)代碼,學(xué)習(xí)c#的朋友可以參考下2012-03-03C#中的lock、Monitor、Mutex學(xué)習(xí)筆記
這篇文章主要介紹了C#中的lock、Monitor、Mutex學(xué)習(xí)筆記,本文講解的都是線程同步的一些知識(shí),需要的朋友可以參考下2015-01-01C#基礎(chǔ)知識(shí)之字符串和正則表達(dá)式
目前為止許多編程語(yǔ)言和工具都包含對(duì)正則表達(dá)式的支持,C#也不例外,下面這篇文章主要給大家介紹了關(guān)于C#基礎(chǔ)知識(shí)之字符串和正則表達(dá)式的相關(guān)資料,需要的朋友可以參考下2022-10-10C#入門(mén)之定義類成員與接口實(shí)現(xiàn)
這篇文章介紹了C#入門(mén)之定義類成員與接口實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-05-05C#中IEnumerable、ICollection、IList、List之間的區(qū)別
IEnumerable、ICollection、IList、List之間的區(qū)別,本文分別分析了它的實(shí)現(xiàn)源碼,從而總結(jié)出了它們之間的關(guān)系和不同之處。對(duì)C# IEnumerable、ICollection、IList、List相關(guān)知識(shí),感興趣的朋友一起看看吧2021-07-07