您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C#怎么利用后綴表達(dá)式解析計(jì)算字符串公式”的有關(guān)知識,在實(shí)際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
當(dāng)我們拿到一個(gè)字符串比如:20+31*(100+1)
的時(shí)候用口算就能算出結(jié)果為3151
,因?yàn)檫@是中綴表達(dá)式對于人類的思維很簡單,但是對于計(jì)算機(jī)就比較復(fù)雜了。相對的后綴表達(dá)式適合計(jì)算機(jī)進(jìn)行計(jì)算。
我們就從簡單到復(fù)雜,逐步實(shí)現(xiàn)對公式的解析(下述的代碼沒有經(jīng)過嚴(yán)格驗(yàn)證,可能會存在極端情況的BUG,作為一種思路僅供參考,商用環(huán)境還需細(xì)細(xì)修改)。
我們從實(shí)現(xiàn)簡單的數(shù)字的加減乘除開始主要是提供一個(gè)思路有需要可以自己修改擴(kuò)展比如增加函數(shù)、字符串、數(shù)組等(推薦一個(gè)項(xiàng)目寫的感覺就不錯(cuò)https://github.com/KovtunV/NoStringEvaluating),那么我們只需要關(guān)注加減乘除等操作符、左右括號和操作數(shù)(整數(shù)、小數(shù)和負(fù)數(shù)),所以我們先建立三個(gè)枚舉類BracketEnum
、NodeTypeEnum
和OperatorEnum
如下:
BracketEnum
是括號枚舉,也就是左右括號"()"
public enum BracketEnum { /// <summary> /// Undefined /// </summary> Undefined = 0, /// <summary> /// 左括號 /// </summary> Open, /// <summary> /// 右括號 /// </summary> Close }
NodeTypeEnum
是節(jié)點(diǎn)類型枚舉,就簡單分為操作符、操作數(shù)和括號
public enum NodeTypeEnum { /// <summary> /// Null /// </summary> Null = 0, /// <summary> /// 操作數(shù) /// </summary> Number, /// <summary> /// 操作符 /// </summary> Operator, /// <summary> /// 括號 /// </summary> Bracket, }
OperatorEnum
是操作符枚舉,主要就是加減乘除這些簡單的
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ì)算
根據(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
類,分別是括號節(jié)點(diǎn)信息、操作數(shù)節(jié)點(diǎn)新和操作符節(jié)點(diǎn)信息,它們各有自己的具體實(shí)現(xiàn),如下:
public class BracketNode : BaseNode { /// <summary> /// 括號值 /// </summary> public BracketEnum Bracket { get; } /// <summary> /// 公式括號節(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)先級 /// </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)信息類,那我們肯定還要有對應(yīng)的解析類分別是BracketReader(括號解析)
、NumberReader(操作數(shù)解析)
和OperatorReader(操作符解析)
,解析類就是為了將公式字符串解析為對應(yīng)的節(jié)點(diǎn)信息具體如下:
public static class BracketReader { /// <summary> /// 左右括號字符 /// </summary> private const char OPEN_BRACKET_CHAR = '('; private const char CLOSE_BRACKET_CHAR = ')'; /// <summary> /// 嘗試獲取左括號 /// </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> /// 嘗試獲取右括號 /// </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> /// 獲取對應(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; }
轉(zhuǎn)為后綴表達(dá)式需要執(zhí)行以下條件:
首先需要分配2個(gè)棧,一個(gè)作為臨時(shí)存儲運(yùn)算符的棧S1(含一個(gè)結(jié)束符號),一個(gè)作為存放結(jié)果(逆波蘭式)的棧S2(空棧),S1??上确湃雰?yōu)先級最低的運(yùn)算符#,注意,中綴式應(yīng)以此最低優(yōu)先級的運(yùn)算符結(jié)束。可指定其他字符,不一定非#不可。從中綴式的左端開始取字符,逐序進(jìn)行如下步驟:
(1)若取出的字符是操作數(shù),則分析出完整的運(yùn)算數(shù),該操作數(shù)直接送入S2棧。
(2)若取出的字符是運(yùn)算符,則將該運(yùn)算符與S1棧棧頂元素比較,如果該運(yùn)算符(不包括括號運(yùn)算符)優(yōu)先級高于S1棧棧頂運(yùn)算符(包括左括號)優(yōu)先級,則將該運(yùn)算符進(jìn)S1棧,否則,將S1棧的棧頂運(yùn)算符彈出,送入S2棧中,直至S1棧棧頂運(yùn)算符(包括左括號)低于(不包括等于)該運(yùn)算符優(yōu)先級時(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)算符(包括左括號)優(yōu)先級,如果棧頂?shù)倪\(yùn)算符優(yōu)先級大于等于該運(yùn)算符的優(yōu)先級,則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; }
以(a+b)*c為例子進(jìn)行說明:
(a+b)*c的逆波蘭式為ab+c*,假設(shè)計(jì)算機(jī)把a(bǔ)b+c*按從左到右的順序壓入棧中,并且按照遇到運(yùn)算符就把棧頂兩個(gè)元素出棧,執(zhí)行運(yùn)算,得到的結(jié)果再入棧的原則來進(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)過以上運(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)行加減乘除簡單的計(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ì)算對后綴表達(dá)式求值 var result = CalculationRPN(rpnNodes); return result; }
“C#怎么利用后綴表達(dá)式解析計(jì)算字符串公式”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。