4

C#后缀表达式解析计算字符串公式 - 以往清泉

 1 year ago
source link: https://www.cnblogs.com/xwc1996/p/17143880.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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

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

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

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

ContractedBlock.gifExpandedBlockStart.gif

View Code

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

ContractedBlock.gifExpandedBlockStart.gif

View Code

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

ContractedBlock.gifExpandedBlockStart.gif

View Code

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

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

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

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

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

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

ContractedBlock.gifExpandedBlockStart.gif

View Code

ContractedBlock.gifExpandedBlockStart.gif

View Code

ContractedBlock.gifExpandedBlockStart.gif

View Code

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

ContractedBlock.gifExpandedBlockStart.gif

View Code

ContractedBlock.gifExpandedBlockStart.gif

View Code

ContractedBlock.gifExpandedBlockStart.gif

View Code

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

        /// <summary>
        /// 解析公式为节点
        /// </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、转为后缀表达式

转为后缀表达式需要执行以下条件：

首先需要分配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栈。
具体实现代码如下：

ContractedBlock.gifExpandedBlockStart.gif

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出栈，执行d*c的操作，得到结果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 in nodes)
            {
                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 as OperatorNode;
                    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(new NumberNode(value));
                }
            }
            result = (stack.Pop() as NumberNode).Number;
            return result;
        }

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

ContractedBlock.gifExpandedBlockStart.gif

View Code

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

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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK