C#利用后綴表達式解析計算字符串公式
更新時間：2023年02月23日 08:30:03 作者：以往清泉
當我們拿到一個字符串比如：20+31*(100+1)的時候用口算就能算出結果為3151，因為這是中綴表達式對于人類的思維很簡單，但是對于計算機就比較復雜了。相對的后綴表達式適合計算機進行計算。本文就來用后綴表達式實現(xiàn)解析計算字符串公式，需要的可以參考一下
當我們拿到一個字符串比如：20+31*(100+1)的時候用口算就能算出結果為3151，因為這是中綴表達式對于人類的思維很簡單，但是對于計算機就比較復雜了。相對的后綴表達式適合計算機進行計算。
我們就從簡單到復雜，逐步實現(xiàn)對公式的解析(下述的代碼沒有經過嚴格驗證，可能會存在極端情況的BUG，作為一種思路僅供參考，商用環(huán)境還需細細修改)。
實現(xiàn)簡單的數(shù)字的加減乘除
我們從實現(xiàn)簡單的數(shù)字的加減乘除開始主要是提供一個思路有需要可以自己修改擴展比如增加函數(shù)、字符串、數(shù)組等（推薦一個項目寫的感覺就不錯https://github.com/KovtunV/NoStringEvaluating），那么我們只需要關注加減乘除等操作符、左右括號和操作數(shù)(整數(shù)、小數(shù)和負數(shù))，所以我們先建立三個枚舉類BracketEnum、NodeTypeEnum和OperatorEnum如下：
BracketEnum是括號枚舉，也就是左右括號"()"
public enum BracketEnum
{
/// <summary>
/// Undefined
/// </summary>
Undefined = 0,
/// <summary>
/// 左括號
/// </summary>
Open,
/// <summary>
/// 右括號
/// </summary>
Close
}NodeTypeEnum是節(jié)點類型枚舉，就簡單分為操作符、操作數(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,
}然后我們需要做以下三步：
- 解析公式將字符轉化為便于操作的節(jié)點信息
- 進行解析為后綴表達式
- 進行計算
1、解析公式轉為節(jié)點信息
根據我們的NodeTypeEnum節(jié)點類型枚舉我們需要三個不同的節(jié)點信息類方便我們的操作，我們先創(chuàng)建基類BaseNode以后的節(jié)點類都繼承它
public class BaseNode
{
public BaseNode(NodeTypeEnum nodeType)
{
NodeType = nodeType;
}
/// <summary>
/// 節(jié)點類型
/// </summary>
public NodeTypeEnum NodeType { get; set; }
}然后我們分別創(chuàng)建BracketNode、NumberNode和OperatorNode類，分別是括號節(jié)點信息、操作數(shù)節(jié)點新和操作符節(jié)點信息，它們各有自己的具體實現(xiàn)，如下：
public class BracketNode : BaseNode
{
/// <summary>
/// 括號值
/// </summary>
public BracketEnum Bracket { get; }
/// <summary>
/// 公式括號節(jié)點
/// </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é)點信息類，那我們肯定還要有對應的解析類分別是BracketReader(括號解析)、NumberReader(操作數(shù)解析)和OperatorReader(操作符解析)，解析類就是為了將公式字符串解析為對應的節(jié)點信息具體如下：
public static class BracketReader
{
/// <summary>
/// 左右括號字符
/// </summary>
private const char OPEN_BRACKET_CHAR = '(';
private const char CLOSE_BRACKET_CHAR = ')';
/// <summary>
/// 嘗試獲取左括號
/// </summary>
/// <param name="nodes">公式節(jié)點信息</param>
/// <param name="formula">公式字符</param>
/// <param name="index">公式讀取的下標</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é)點信息</param>
/// <param name="formula">公式字符</param>
/// <param name="index">公式讀取的下標</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;//是否轉換成功
var isNegative = formula[index] == '-';//是否是負數(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))
{
//如果最后一個并且成功
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)
{
//是不是十進制數(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>
/// 獲取對應枚舉
/// </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
};
}
}有了以上的準備，我們就可以將公式轉為我們的節(jié)點信息了如下
/// <summary>
/// 解析公式為節(jié)點
/// </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、轉為后綴表達式
轉為后綴表達式需要執(zhí)行以下條件：
首先需要分配2個棧，一個作為臨時存儲運算符的棧S1（含一個結束符號），一個作為存放結果（逆波蘭式）的棧S2（空棧），S1?？上确湃雰?yōu)先級最低的運算符#，注意，中綴式應以此最低優(yōu)先級的運算符結束?？芍付ㄆ渌址?，不一定非#不可。從中綴式的左端開始取字符，逐序進行如下步驟：
（1）若取出的字符是操作數(shù)，則分析出完整的運算數(shù)，該操作數(shù)直接送入S2棧。
（2）若取出的字符是運算符，則將該運算符與S1棧棧頂元素比較，如果該運算符(不包括括號運算符)優(yōu)先級高于S1棧棧頂運算符（包括左括號）優(yōu)先級，則將該運算符進S1棧，否則，將S1棧的棧頂運算符彈出，送入S2棧中，直至S1棧棧頂運算符（包括左括號）低于（不包括等于）該運算符優(yōu)先級時停止彈出運算符，最后將該運算符送入S1棧。
（3）若取出的字符是“（”，則直接送入S1棧頂。
（4）若取出的字符是“）”，則將距離S1棧棧頂最近的“（”之間的運算符，逐個出棧，依次送入S2棧，此時拋棄“（”。
（5）重復上面的1~4步，直至處理完所有的輸入字符。
（6）若取出的字符是“#”，則將S1棧內所有運算符（不包括“#”），逐個出棧，依次送入S2棧。
具體實現(xiàn)代碼如下：
/// <summary>
/// 轉為后綴表達式
/// </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、若取出的字符是運算符,則循環(huán)比較S1棧頂?shù)倪\算符（包括左括號）優(yōu)先級，如果棧頂?shù)倪\算符優(yōu)先級大于等于該運算符的優(yōu)先級，則S1棧頂運算符彈出加入到S2中直至不滿足條件為止，最后將該運算符送入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棧棧頂最近的“（”之間的運算符，逐個出棧，依次送入S2棧，此時拋棄“（”。
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、重復上述步驟
}
if(tempNodes.Count > 0)
{
rpnNodes.Add(tempNodes.Pop());
}
return rpnNodes;
}3、計算后綴表達式
以(a+b)*c為例子進行說明：
(a+b)*c的逆波蘭式為ab+c*，假設計算機把ab+c*按從左到右的順序壓入棧中，并且按照遇到運算符就把棧頂兩個元素出棧，執(zhí)行運算，得到的結果再入棧的原則來進行處理，那么ab+c*的執(zhí)行結果如下：
1）a入棧（0位置）
2）b入棧（1位置）
3）遇到運算符“+”，將a和b出棧，執(zhí)行a+b的操作，得到結果d=a+b，再將d入棧（0位置）
4）c入棧（1位置）
5）遇到運算符“*”，將d和c出棧，執(zhí)行d*c的操作，得到結果e，再將e入棧（0位置）
經過以上運算，計算機就可以得到(a+b)*c的運算結果e了。
具體實現(xiàn)代碼如下：
/// <summary>
/// 計算后綴表達式
/// </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)
{
//操作符彈出棧頂兩個進行計算
var a = stack.Pop();
var b = stack.Pop();
var operate = t as OperatorNode;
var value = operate.OperatorKey switch
{
// 數(shù)學操作符
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ù)學操作符執(zhí)行代碼如下主要為了進行加減乘除簡單的計算：
/// <summary>
/// 操作符服務
/// </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ù)字類型，并返回數(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
}最后串在一起就能得到結果啦，就像下面這樣
/// <summary>
/// 計算
/// </summary>
/// <param name="formula">公式字符串</param>
/// <returns></returns>
public static double Calculation(string formula)
{
//1、獲取公式節(jié)點
var nodes = AnalysisFormulaToNodes(formula);
//2、轉后綴表達式
var rpnNodes = GetRPN(nodes);
//3、計算對后綴表達式求值
var result = CalculationRPN(rpnNodes);
return result;
}到此這篇關于C#利用后綴表達式解析計算字符串公式的文章就介紹到這了,更多相關C#解析計算字符串公式內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
c#中的浮點型轉整形的舍取 四舍五入和銀行家舍入實現(xiàn)代碼
c#中的浮點型轉整形的舍取 四舍五入和銀行家舍入實現(xiàn)代碼，學習c#的朋友可以參考下2012-03-03
我們很多時候會碰到這樣的問題，使用多線程刷一個表的數(shù)據時需要多個線程不能重復提取數(shù)據，那么這個時候就需要使用到線程的排他鎖了，本文就詳細的介紹一下2021-08-08
這篇文章主要為大家詳細介紹了C#單線程和多線程端口掃描器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
這篇文章主要介紹了C#中的lock、Monitor、Mutex學習筆記,本文講解的都是線程同步的一些知識,需要的朋友可以參考下2015-01-01
目前為止許多編程語言和工具都包含對正則表達式的支持,C#也不例外,下面這篇文章主要給大家介紹了關于C#基礎知識之字符串和正則表達式的相關資料,需要的朋友可以參考下2022-10-10
這篇文章介紹了C#入門之定義類成員與接口實現(xiàn)，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-05-05
這篇文章主要為大家詳細介紹了C# 7.0中的解構功能，解構元組、解構對象等，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-08-08
這篇文章主要介紹了C#?Chart控件標記問題詳解，在做項目的時候，遇到一個需求，需要我對Chart圖標標記數(shù)據正在運行，實現(xiàn)數(shù)據可視化，文章通過圍繞主題展開詳情，需要的朋友可以參考一下2022-08-08
C#中IEnumerable、ICollection、IList、List之間的區(qū)別
IEnumerable、ICollection、IList、List之間的區(qū)別,本文分別分析了它的實現(xiàn)源碼,從而總結出了它們之間的關系和不同之處。對C# IEnumerable、ICollection、IList、List相關知識，感興趣的朋友一起看看吧2021-07-07
本文詳細講解了C#中委托的用法，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-02-02