借助表达式树对四则运算表达式进行计算

若何盘算像这样的一个算术表达式:
-5+(-5)+35^3+14*(52+9)

学过数据结构的我们知道, 这是一个中缀表达式, 我们可以先把它转成前缀或者后缀表达式, 然后盘算起来就比较简朴了;

这里我使用后缀表达式来实现;

准备知识

  1. 数据结构 – 二叉树
  2. 设计模式 – 制作者 计谋
  3. C#中的表达式树(Expression)

从后缀表达式天生表达式树

后缀表达式怎么天生表达式树?

我参考了 <<数据结构与算法剖析-C语言形貌>> 中给出的一个算法来实现将后缀表达式转化成C#中的 Expression:

遍历后缀表达式字符串数组, 判断当前是操作符照样操作数, 若是是操作数, 则组织ConstantExpression然后压栈, 若是是操作符, 则出两次栈, 组织一个BinaryExpression然后将其压栈;

这里使用了制作者模式, 构建表达式树的函数放在了制作者类内里, 完整的代码地址在文末给出了;

/// <summary>
/// 从后缀表达式天生一个表达式树
/// </summary>
/// <param name="postFix">后缀表达式</param>
private void BuildExpressionFromPostFix(string[] postFix)
{
    var stack = new Stack<Expression>();

    BinaryExpression ex;
    Expression l, r;
    for (int i = 0;i < postFix.Length;i++)
    {
        if(IsArithmetricOperator(postFix[i]))
        {
            r = stack.Pop();
            l = stack.Pop();
            ex = Expression.MakeBinary(
                ArthmetricOperatorsMapping[postFix[i][0]],
                l, r);

            stack.Push(ex);
        }
        else
        {
            stack.Push(
                Expression.Constant(
                    double.Parse(postFix[i])));
        }
    }
    if (stack.Peek() is BinaryExpression binaryExpression)
        _exprTree = binaryExpression;
    else if (stack.Peek() is ConstantExpression constantExpression)
        _exprTree = Expression.Add(constantExpression, Expression.Constant(0d)); // 单独一个表达式 5 
}

中缀表达式转成后缀表达式

这里输入的中缀表达式是一个字符串, 输出一个字符串数组保留后缀表达式

【Transferable NAS with RL】2018-CVPR-Learning Transferable Architectures for Scalable Image Recognition

<<数据结构与算法剖析-C语言形貌>> 这本书在栈的那一章给出了中缀表达式转后缀表达式的算法, 简朴来说就是:
遇到操作数, 操作数放到效果集内里去;
遇到运算符, 判断是否要压栈, 压栈的条件是

  1. 若是当前栈空, 则压栈
  2. 栈顶的操作符优先级低于当前操作符的优先级, 则压栈
    出栈的条件:
  3. 栈顶元素优先级高于或即是当前操作符的优先级, 则出栈直到栈顶元素优先级低于当前操作符, 然后将当前操作符入栈;

详细代码, 写的欠好, 迎接指正, 内里用到了制作者的成员变量, 完整代码看文末链接:

/// <summary>
/// 构建后缀表达式
/// </summary>
private void BuildPostFixExpr()
{
    if (_postFixExpr == null)
    {
        var stack = new Stack<char>();
        int sIndex = 0;
        var list = new List<string>();

        // 表达式开头可能泛起 "-" 号
        if (_expr.Length > 0 && IsArithmetricOperator(_expr[0]))
            _expr = _expr.Insert(0, "0");

        for (int i = 0; i< _expr.Length; i++)
        {
            if (IsArithmetricOperator(_expr[i]))
            {
                sIndex = i + 1;
                if (stack.Count <= 0)
                {
                    stack.Push(_expr[i]);
                }
                else
                {
                    if (_expr[i] == ')')
                    {
                        while (stack.Peek() != '(')
                        {
                            list.Add(stack.Pop().ToString());
                        }
                        stack.Pop();
                    }
                    else if(i+1 < _expr.Length && _expr[i] == '(' && 
                        _expr[i+1] != '(' && IsArithmetricOperator(_expr[i+1]))
                    {
                        _expr = _expr.Insert(i+1, "0");   // 5-(-5) 的情形
                        stack.Push(_expr[i]);
                    }
                    else if (stack.Peek() != '(' && ArithmetricOperatorsPriority[stack.Peek()] >=
                                ArithmetricOperatorsPriority[_expr[i]])
                    {
                        while (stack.Count > 0 && stack.Peek() != '(' && ArithmetricOperatorsPriority[stack.Peek()] >=
                                ArithmetricOperatorsPriority[_expr[i]])
                            list.Add(stack.Pop().ToString());
                        stack.Push(_expr[i]);
                    }
                    else
                        stack.Push(_expr[i]);
                }
            }
            else
            {
                if ((_expr.Length > i+1 && IsArithmetricOperator(_expr[i+1])) || i == _expr.Length - 1)
                    list.Add(_expr.Substring(sIndex, i-sIndex+1));
            }
        }

        while (stack.Count > 0)
        {
            if (stack.Peek() == '(')
            {
                stack.Pop();
                continue;
            }
            list.Add(stack.Pop().ToString());
        }
        _postFixExpr = list.ToArray();
    }
}

获得了使用Expression组成的表达式树, 若何盘算最终效果呢

上面我们完成了基于Expression的表达式树的构建, 需要注重的是, Expression类是一个抽象类, 我们上面的构建的表达式树主要用到了他的两个派生类: ConstantExpressionBinaryExpression, 其中BinaryExpression实在就是一个二叉树节点, 而ConstantExpression呢, 顾名思义,就是一个保留了操作数的常量表达式;

以是最终若何盘算获得表达式的效果呢?

有两种设施:

这里的话我使用了计谋模式来封装这两种方案

计谋接口:IExpressionTreeCalculatorEngine

using System.Linq.Expressions;

namespace SimpleCalculator
{
    internal interface IExpressionTreeCalculatorEngine
    {
        double Calculate(Expression expression);
    }
}

DefaultCalculatorEngine计谋

这个计谋比较简朴, 直接将作为参数的通报过来的表达式通过 Expression.Lambda() 天生 lambda 表达式然后编译并挪用获得最终效果;

using System;
using System.Linq.Expressions;

namespace SimpleCalculator
{
    internal class DefaultCalculatorEngine : IExpressionTreeCalculatorEngine
    {
        public double Calculate(Expression expression)
        {
            Func<double> calculate = Expression.Lambda<Func<double>>(expression).Compile();
            return calculate();
        }
    }
}

自己手动后序遍历递归求值(RecursionExpressionTreeCalculatorEngine)

using System;
using System.Diagnostics;
using System.Linq.Expressions;

namespace SimpleCalculator
{
    internal sealed class RecursionExpressionTreeCalculatorEngine : ExpressionVisitor,IExpressionTreeCalculatorEngine
    {

        public double Calculate(Expression expression)
        {
            Expression exp = Visit(expression);
            var constant = exp as ConstantExpression;
            return (double)constant.Value;
        }

        protected override Expression VisitBinary(BinaryExpression node)
        {
            Expression l = Visit(node.Left);
            Expression r = Visit(node.Right);
            
            if (l is ConstantExpression cl && r is ConstantExpression cr)
                switch (node.NodeType)
                {
                    case ExpressionType.Add:
                        Debug.Write($"(+{cl.Value} {cr.Value})");
                        return Expression.Constant((double)cl.Value+(double)cr.Value);
                    case ExpressionType.Divide:
                        Debug.Write($"(/{cl.Value} {cr.Value})");
                        return Expression.Constant((double)cl.Value/(double)cr.Value);
                    case ExpressionType.Subtract:
                        Debug.Write($"(-{cl.Value} {cr.Value})");
                        return Expression.Constant((double)cl.Value-(double)cr.Value);
                    case ExpressionType.Multiply:
                        Debug.Write($"(*{cl.Value} {cr.Value})");
                        return Expression.Constant((double)cl.Value*(double)cr.Value);
                    case ExpressionType.PowerAssign:
                    case ExpressionType.Power:
                        Debug.Write($"(^{cl.Value} {cr.Value})");
                        return Expression.Constant(Math.Pow((double)cl.Value, (double)cr.Value));
                    case ExpressionType.Modulo:
                        Debug.Write($"(/{cl.Value} {cr.Value})");
                        return Expression.Constant((double)cl.Value%(double)cr.Value);
                    //case ExpressionType
                    default:
                        throw new NotSupportedException();
                }
            else
            {
                Debug.Write(node.ToString());
                return node;
            }
        }

        protected override Expression VisitConstant(ConstantExpression node)
        {
            return node;
        }
    }
}

这个类通过继续 ExpressionVisitor 来递归遍历各个表达式节点, 类似二叉树的后序遍历;

查看完整代码

原创文章,作者:dddof新闻网,如若转载,请注明出处:https://www.dddof.com/archives/18875.html