C#后缀表达式解析计算字符串公式

转x33g5p2x  于5个月前 转载在 C#  
字(10.9k)|赞(0)|评价(0)|浏览(186)

当我们拿到一个字符串比如： 20+31*(100+1) 的时候用口算就能算出结果为 3151 ，因为这是 中缀表达式 对于人类的思维很简单，但是对于计算机就比较复杂了。相对的 后缀表达式 适合计算机进行计算。

我们就从简单到复杂，逐步实现对公式的解析(下述的代码没有经过严格验证，可能会存在极端情况的BUG，作为一种思路仅供参考，商用环境还需细细修改)。

实现简单的数字的加减乘除

我们从实现简单的数字的加减乘除开始***主要是提供一个思路有需要可以自己修改扩展比如增加函数、字符串、数组等（推荐一个项目写的感觉就不错https://github.com/KovtunV/NoStringEvaluating）***，那么我们只需要关注加减乘除等操作符、左右括号和操作数(整数、小数和负数)，所以我们先建立三个枚举类 BracketEnum 、 NodeTypeEnum 和 OperatorEnum 如下：

BracketEnum 是括号枚举，也就是左右括号"()"

public enumBracketEnum
{
    /// <summary>
    ///Undefined
    /// </summary>
    Undefined = 0,
    /// <summary>
    ///左括号
    /// </summary>
Open,
    /// <summary>
    ///右括号
    /// </summary>
Close
}

View Code

NodeTypeEnum 是节点类型枚举，就简单分为操作符、操作数和括号

public enumNodeTypeEnum
{
    /// <summary>
    ///Null
    /// </summary>
    Null = 0,
    /// <summary>
    ///操作数
    /// </summary>
Number,
    /// <summary>
    ///操作符
    /// </summary>
Operator,
    /// <summary>
    ///括号
    /// </summary>
Bracket,
}

View Code

OperatorEnum 是操作符枚举，主要就是加减乘除这些简单的

public enumOperatorEnum
{
    /// <summary>
    ///Undefined
    /// </summary>
    Undefined = 0,
    /// <summary>
    ///+
    /// </summary>
Plus,
    /// <summary>
    ///-
    /// </summary>
Minus,
    /// <summary>
    ///*
    /// </summary>
Multiply,
    /// <summary>
    ////
    /// </summary>
Divide,
    /// <summary>
    ///^
    /// </summary>
Power,
}

View Code

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

  1. 解析公式将字符转化为便于操作的节点信息
  2. 进行解析为后缀表达式
  3. 进行计算

** 1、解析公式转为节点信息**

根据我们的 NodeTypeEnum 节点类型枚举我们需要三个不同的节点信息类方便我们的操作，我们先创建基类 BaseNode 以后的节点类都继承它

public classBaseNode
    {
        publicBaseNode(NodeTypeEnum nodeType)
        {
            NodeType =nodeType;
        }
        /// <summary>
        ///节点类型
        /// </summary>
        public NodeTypeEnum NodeType { get; set; }
    }

然后我们分别创建 BracketNode 、 NumberNode 和 OperatorNode 类，分别是括号节点信息、操作数节点新和操作符节点信息，它们各有自己的具体实现，如下：

public classBracketNode : BaseNode
    {
        /// <summary>
        ///括号值
        /// </summary>
        public BracketEnum Bracket { get; }
        /// <summary>
        ///公式括号节点
        /// </summary>
        public BracketNode(BracketEnum bracket) : base(NodeTypeEnum.Bracket)
        {
            Bracket =bracket;
        }
    }

View Code

public classNumberNode : BaseNode
    {
        /// <summary>
        ///数字值
        /// </summary>
        public double Number { get; }
        public NumberNode(double number) : base(NodeTypeEnum.Number)
        {
            Number =number;
        }
    }

View Code

public classOperatorNode : BaseNode
    {
        /// <summary>
        ///操作字符串枚举
        /// </summary>
        public OperatorEnum OperatorKey { get; }
        /// <summary>
        ///优先级
        /// </summary>
        public int Priority { get; }
        public OperatorNode(OperatorEnum operatorKey) : base(NodeTypeEnum.Operator)
        {
            OperatorKey =operatorKey;
            Priority =GetPriority();
        }
        private intGetPriority()
        {
            var priority = OperatorKey switch{
                OperatorEnum.Power => 6,
                OperatorEnum.Multiply => 5,
                OperatorEnum.Divide => 5,
                OperatorEnum.Plus => 4,
                OperatorEnum.Minus => 4,
                _ => 0};
            returnpriority;
        }
    }

View Code

有了节点信息类，那我们肯定还要有对应的解析类分别是 BracketReader(括号解析) 、 NumberReader(操作数解析) 和 OperatorReader(操作符解析) ，解析类就是为了将公式字符串解析为对应的节点信息具体如下：

public static classBracketReader
    {
        /// <summary>
        ///左右括号字符
        /// </summary>
        private const char OPEN_BRACKET_CHAR = '(';
        private const char CLOSE_BRACKET_CHAR = ')';
        /// <summary>
        ///尝试获取左括号
        /// </summary>
        /// <param name="nodes">公式节点信息</param>
        /// <param name="formula">公式字符</param>
        /// <param name="index">公式读取的下标</param>
        /// <returns></returns>
        public static bool TryProceedOpenBracket(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref intindex)
        {
            if(formula[index].Equals(OPEN_BRACKET_CHAR))
            {
                nodes.Add(newBracketNode(BracketEnum.Open));
                return true;
            }
            return false;
        }
        /// <summary>
        ///尝试获取右括号
        /// </summary>
        /// <param name="nodes">公式节点信息</param>
        /// <param name="formula">公式字符</param>
        /// <param name="index">公式读取的下标</param>
        /// <returns></returns>
        public static bool TryProceedCloseBracket(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref intindex)
        {
            if(formula[index].Equals(CLOSE_BRACKET_CHAR))
            {
                nodes.Add(newBracketNode(BracketEnum.Close));
                return true;
            }
            return false;
        }
    }

View Code

public static classNumberReader
    {
        /// <summary>
        ///尝试读取数字
        /// </summary>
        public static bool TryProceedNumber(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref intindex)
        {
            double value = 0;
            var isTry = false;//是否转换成功
            var isNegative = formula[index] == '-';//是否是负数
            var localIndex = isNegative ? index + 1: index;
            //循环判断数字
            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), outvalue))
                    {
                        index =i;
                        isTry = true;
                        break;
                    }
                }
                else if(double.TryParse(formula.Slice(index, i - index), outvalue))
                {
                    //如果不是数字比如是字母，则直接判断之前的数字
                    index = i - 1;
                    isTry = true;
                    break;
                }
                else{
                    break;
                }
            }
            if(isTry)
            {
                nodes.Add(newNumberNode(value));
            }
            returnisTry;
        }
        /// <summary>
        ///判断是不是数字或者.
        /// </summary>
        /// <param name="ch">字符</param>
        /// <returns></returns>
        private static bool IsFloatingNumber(charch)
        {
            //是不是十进制数
            var isDigit = char.IsDigit(ch);
            return isDigit || ch == '.';
        }
    }

View Code

/// <summary>
    ///操作符解读
    /// </summary>
    public static classOperatorReader
    {
        private static readonly string[] _operators = new[] { "+", "-", "*", "/", "^"};

        /// <summary>
        ///尝试获取操作符
        /// </summary>
        public static bool TryProceedOperator(List<BaseNode> nodes, ReadOnlySpan<char> formula, ref intindex)
        {
            if(_operators.Contains(formula[index].ToString()))
            {
                nodes.Add(newOperatorNode(GetOperatorKey(formula[index].ToString())));
                return true;
            }
            return false;
        }
        /// <summary>
        ///获取对应枚举
        /// </summary>
        /// <param name="name"></param>
        /// <returns></returns>
        private static OperatorEnum GetOperatorKey(stringname)
        {
            return name switch{
                "+" =>OperatorEnum.Plus,
                "-" =>OperatorEnum.Minus,
                "*" =>OperatorEnum.Multiply,
                "/" =>OperatorEnum.Divide,
                "^" =>OperatorEnum.Power,

                _ =>OperatorEnum.Undefined
            };
        }
    }

View Code

有了以上的准备，我们就可以将公式转为我们的节点信息了如下

/// <summary>
        ///解析公式为节点
        /// </summary>
        /// <param name="formula">公式字符串</param>
        /// <returns></returns>
        public static List<BaseNode> AnalysisFormulaToNodes(stringformula)
        {
            var nodes = new List<BaseNode>();
            for(var index = 0;index< formula.Length; index++)
            {
                if (NumberReader.TryProceedNumber(nodes, formula.AsSpan(), refindex))
                    continue;
                if (OperatorReader.TryProceedOperator(nodes, formula.AsSpan(), refindex))
                    continue;
                if (BracketReader.TryProceedOpenBracket(nodes, formula.AsSpan(), refindex))
                    continue;
                if (BracketReader.TryProceedCloseBracket(nodes, formula.AsSpan(), refindex))
                    continue;
            }
            returnnodes;
        }

** 2、转为后缀表达式**

转为后缀表达式需要执行以下条件：
首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为存放结果（逆波兰式）的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：

（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈。
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。

（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。

（5）重复上面的1~4步，直至处理完所有的输入字符。
（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。

具体实现代码如下：

/// <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 innodes)
            {
                //1、如果是操作数直接入栈
                if(t.NodeType ==NodeTypeEnum.Number)
                {
                    rpnNodes.Add(t);
                    continue;
                }
                //2、若取出的字符是运算符,则循环比较S1栈顶的运算符（包括左括号）优先级，如果栈顶的运算符优先级大于等于该运算符的优先级，则S1栈顶运算符弹出加入到S2中直至不满足条件为止，最后将该运算符送入S1中。
                if (t.NodeType ==NodeTypeEnum.Operator)
                {
                    while (tempNodes.Count > 0)
                    {
                        var peekOperatorNode = tempNodes.Peek() asOperatorNode;
                        if (peekOperatorNode != null && peekOperatorNode.Priority >= (t asOperatorNode).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() asBracketNode;
                            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());
            }
            returnrpnNodes;
        }

View Code

3、计算后缀表达式

以(a+b)*c为例子进行说明：

(a+b)c的逆波兰式为ab+c，假设计算机把ab+c按从左到右的顺序压入栈中，并且按照遇到 运算符 就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理，那么ab+c的执行结果如下：
1）a入栈（0位置）

2）b入栈（1位置）
3）遇到运算符“+”，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置）

4）c入栈（1位置）
5）遇到运算符“”，将d和c出栈，执行dc的操作，得到结果e，再将e入栈（0位置）

经过以上运算，计算机就可以得到(a+b)*c的运算结果e了。
具体实现代码如下：

/// <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 innodes)
            {
                if(t.NodeType ==NodeTypeEnum.Number)
                {
                    //操作数直接入栈
stack.Push(t);
                }
                else if(t.NodeType ==NodeTypeEnum.Operator)
                {
                    //操作符弹出栈顶两个进行计算
                    var a =stack.Pop();
                    var b =stack.Pop();
                    var operate = t asOperatorNode;
                    var value = operate.OperatorKey switch{
                        //数学操作符
                        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(newNumberNode(value));
                }
            }
            result = (stack.Pop() asNumberNode).Number;
            returnresult;
        }

数学操作符执行代码如下主要为了进行加减乘除简单的计算：

/// <summary>
    ///操作符服务
    /// </summary>
    public static classOperatorService
    {
        #region Math

        public static double Multiply(in BaseNode a, inBaseNode b)
        {
            var (result, _a, _b) =IsNumber(a, b);
            if(result)
            {
                return _a *_b;
            }
            return default;
        }

        public static double Divide(in BaseNode a, inBaseNode b)
        {
            var (result, _a, _b) =IsNumber(a, b);
            if(result)
            {
                return _a /_b;
            }
            return default;
        }

        public static double Plus(in BaseNode a, inBaseNode b)
        {
            var (result, _a, _b) =IsNumber(a, b);
            if(result)
            {
                return _a +_b;
            }
            return default;
        }

        public static double Minus(in BaseNode a, inBaseNode b)
        {
            var (result, _a, _b) =IsNumber(a, b);
            if(result)
            {
                return _a -_b;
            }
            return default;
        }

        public static double Power(in BaseNode a, inBaseNode b)
        {
            var (result, _a, _b) =IsNumber(a, b);
            if(result)
            {
                returnMath.Pow(_a, _b);
            }
            return default;
        }
        /// <summary>
        ///判断是不是数字类型，并返回数字
        /// </summary>
        /// <param name="a"></param>
        /// <returns></returns>
        private static (bool,double,double) IsNumber(BaseNode a, inBaseNode b)
        {
            if(a.NodeType == NodeTypeEnum.Number && b.NodeType ==NodeTypeEnum.Number)
            {
                var _a = a asNumberNode;
                var _b = b asNumberNode;
                return (true, _a.Number, _b.Number);
            }
            return (false, default, default);
        }
        #endregion}

View Code

最后串在一起就能得到结果啦，就像下面这样

/// <summary>
        ///计算
        /// </summary>
        /// <param name="formula">公式字符串</param>
        /// <returns></returns>
        public static double Calculation(stringformula)
        {
            //1、获取公式节点
            var nodes =AnalysisFormulaToNodes(formula);
            //2、转后缀表达式
            var rpnNodes =GetRPN(nodes);
            //3、计算对后缀表达式求值
            var result =CalculationRPN(rpnNodes);
            returnresult;
        }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://www.cnblogs.com/xwc1996/p/17143880.html

内容来源于网络，如有侵权，请联系作者删除！

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com