C#利用后綴表達(dá)式解析計(jì)算字符串公式

更新時(shí)間：2023年02月23日 08:30:03 作者：以往清泉

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

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

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

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

我們從實(shí)現(xià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)"()"

public enum BracketEnum
{
    /// <summary>
    /// Undefined
    /// </summary>
    Undefined = 0,
    /// <summary>
    /// 左括號(hào)
    /// </summary>
    Open,
    /// <summary>
    /// 右括號(hào)
    /// </summary>
    Close
}

NodeTypeEnum是節(jié)點(diǎ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是操作符枚舉，主要就是加減乘除這些簡單的

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é)束?？芍付ㄆ渌址?，不一定非#不可。從中綴式的左端開始取字符，逐序進(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)行說明：

(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ì)算對(duì)后綴表達(dá)式求值
            var result = CalculationRPN(rpnNodes);
            return result;
        }

到此這篇關(guān)于C#利用后綴表達(dá)式解析計(jì)算字符串公式的文章就介紹到這了,更多相關(guān)C#解析計(jì)算字符串公式內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: