字串表示式計算(a+b/(a-b))的思路與實踐

前言

為滿足業務需要，需要為專案中自定義模板新增一個計算欄位的元件，通過設定字串表示式，使用時在改變表示式其中一個欄位的資料時，自動計算另外一個欄位的值。

本篇為上篇，介紹原理，簡單實現一個工具，輸入字串表示式，解析其中的引數，輸入引數計算結果。

下篇將基於此封裝實現對Mongo查詢語法的封裝，通過addFields的方式轉換表示式，後續等封裝成NuGet包再分享

實現如下所示

輸入 1+1  輸出 2
輸入 a+1 引數a:1 輸出 2
輸入 (a+1)*b 輸入a:1,b:1 輸出 2
輸入 (a+1-(2+a)*3/3)/a+3 輸入a:1 輸出 2

實現思路

想要實現上面這個功能，需要先了解諸如 (a+1-(2+a)*3/3)/a+3 這個是什麼？

維基百科：中綴表示法（或中綴記法）是一個通用的算術或邏輯公式表示方法，操作符是以中綴形式處於運算元的中間（例：3 + 4）。與字首表示式（例：+ 3 4 ）或字尾表示式（例：3 4 + ）相比，中綴表示式不容易被電腦解析邏輯優先順序，但仍被許多程式語言使用，因為它符合大多數自然語言的寫法。

字首表示法（+ 3 4 ）也叫波蘭表示法

字尾表示法（3 4 + ）也叫逆波蘭表示法

在維基百科的說明中，也給出了和其相關的另外兩種表示法，以及用於把中綴表示式轉換到字尾表示式或樹的演演算法：排程場演演算法，如下圖所示

實現程式碼

找了很多的開源專案，最終基於 qinfengzhu/Evaluator ，實現了上述功能。

呼叫程式碼

using Evaluator;
using System.Text.RegularExpressions;

Console.WriteLine("字串表示式計算工具");
EvalTest();

void EvalTest()
{
    Console.WriteLine("----------------------------------------------------");
    var parse = new EvalParser();
    Console.Write("請輸入表示式：");//a+b*3/5+a
    var evalStr = Console.ReadLine();
    if (string.IsNullOrEmpty(evalStr))
    {
        Console.WriteLine("Game Over");
        return;
    }
    //解析其中的變數並讓使用者輸入
    var matchs = Regex.Matches(evalStr, @"\b[\w$]+\b");
    var paramsDic = new Dictionary<string, object>();
    //預定義引數
    paramsDic.Add("now_year", DateTime.Now.Year);
    paramsDic.Add("now_month", DateTime.Now.Month);
    paramsDic.Add("now_day", DateTime.Now.Day);
    foreach (Match match in matchs)
    {
        if (decimal.TryParse(match.Value, out decimal kp))
            continue;
        if (!paramsDic.ContainsKey(match.Value))
        {
            Console.Write($"請輸入數位變數【{match.Value}】：");
            var paramValue = Console.ReadLine();
            decimal dvalue;
            while (!decimal.TryParse(paramValue, out dvalue))
            {
                Console.WriteLine($"輸入有誤，請輸入數位變數【{match.Value}】：");
                paramValue = Console.ReadLine();
            }
            paramsDic.Add(match.Value, dvalue);
        }
    }
    var result = parse.EvalNumber(evalStr, paramsDic);
    Console.WriteLine($"結果：{result}");
    EvalTest();
}

EvalParser 類的實現

通過上面呼叫程式碼可以看到，核心的計算類是 EvalParser ，呼叫其 EvalNumber 進行計算

EvalNumber 實現

EvalNumber 方法,主要分為3步
- 第一步將表示式解析轉換到佇列中，即將中綴表示式，轉換成字尾表示式
- 第二步將佇列中的表示式加入表示式棧中
- 第三步使用表示式樹進行計算
返回值處理
- 已知的錯誤有除以0和溢位的異常，所以直接捕獲返回null，也可以在計算除數的時候判斷值為0就直接返回null，
- 精度處理

EvalNumber 計算核心程式碼

/// <summary>
/// 計算表示式的計算結果
/// </summary>
/// <param name="expression">表示式</param>
/// <param name="dynamicObject">動態物件</param>
/// <param name="precision">精度 預設2</param>
/// <returns>計算的結果</returns>
public decimal? EvalNumber(string expression, Dictionary<string, object> dynamicObject, int precision = 2)
{
    var values = dynamicObject ?? new Dictionary<string, object>();
    //中綴表示式，轉換成字尾表示式併入列
    var queue = ParserInfixExpression(expression, values);
    var cacheStack = new Stack<Expression>();
    while (queue.Count > 0)
    {
        var item = queue.Dequeue();
        if (item.ItemType == EItemType.Value && item.IsConstant)
        {
            var itemExpression = Expression.Constant(item.Value);
            cacheStack.Push(itemExpression);
            continue;
        }
        if (item.ItemType == EItemType.Value && !item.IsConstant)
        {
            var propertyName = item.Content.Trim();
            //將引數替換回來
            propertyName = PreReplaceTextToOprator(propertyName, values);
            //引數為空的情況
            if (!values.ContainsKey(propertyName) || values[propertyName] == null || !decimal.TryParse(values[propertyName].ToString(), out decimal propertyValue))
                return null;
            //var propertyValue = decimal.Parse(values[propertyName].ToString());
            var itemExpression = Expression.Constant(propertyValue);
            cacheStack.Push(itemExpression);
        }
        if (item.ItemType == EItemType.Operator)
        {
            if (cacheStack.Count <= 1)
                continue;
            Expression firstParamterExpression = Expression.Empty();
            Expression secondParamterExpression = Expression.Empty();
            switch (item.Content[0])
            {
                case EvalParser.AddOprator:
                    firstParamterExpression = cacheStack.Pop();
                    secondParamterExpression = cacheStack.Pop();
                    var addExpression = Expression.Add(secondParamterExpression, firstParamterExpression);
                    cacheStack.Push(addExpression);
                    break;
                case EvalParser.DivOperator:
                    firstParamterExpression = cacheStack.Pop();
                    secondParamterExpression = cacheStack.Pop();
                    var divExpression = Expression.Divide(secondParamterExpression, firstParamterExpression);
                    cacheStack.Push(divExpression);
                    break;
                case EvalParser.MulOperator:
                    firstParamterExpression = cacheStack.Pop();
                    secondParamterExpression = cacheStack.Pop();
                    var mulExpression = Expression.Multiply(secondParamterExpression, firstParamterExpression);
                    cacheStack.Push(mulExpression);
                    break;
                case EvalParser.SubOperator:
                    firstParamterExpression = cacheStack.Pop();
                    secondParamterExpression = cacheStack.Pop();
                    var subExpression = Expression.Subtract(secondParamterExpression, firstParamterExpression);
                    cacheStack.Push(subExpression);
                    break;
                case EvalParser.LBraceOperator:
                case EvalParser.RBraceOperator:
                    continue;
                default:
                    throw new Exception("計算公式錯誤");
            }
        }
    }
    if (cacheStack.Count == 0)
        return null;
    var lambdaExpression = Expression.Lambda<Func<decimal>>(cacheStack.Pop());
    try
    {
        // 除0 溢位
        var value = lambdaExpression.Compile()();
        return Math.Round(value, precision);
    }
    catch (Exception ex)
    {
        //System.OverflowException
        //System.DivideByZeroException
        if (ex is DivideByZeroException
            || ex is OverflowException)
            return null;
        throw ex;
    }
}

ParserInfixExpression 實現

在EvalNumber 方法的第一步呼叫了 ParserInfixExpression 方法來進行表示式的預處理

PreReplaceOpratorToText 如果變數中帶有一些計算符號(+-*/())，通過這個方法轉換臨時變數，在獲取值的時候再轉換回來


/// <summary>
/// 符號轉換字典
/// </summary>
private static Dictionary<char, string> OperatorToTextDic = new Dictionary<char, string>()
{
    { '+', "_JIA_" },
    { '-', "_JIAN_" },
    { '/', "_CHENG_" },
    { '*', "_CHU_" },
    { '(', "_ZKH_" },
    { ')', "_YKH_" }
};
/// <summary>
/// 預處理引數符號轉文字
/// </summary>
/// <param name="expression"></param>
/// <param name="dynamicObject"></param>
/// <returns></returns>
public string PreReplaceOpratorToText(string expression, Dictionary<string, object> dynamicObject)
{
    //如果是引數裡面包含了括號,將其中的引數替換成特殊字元
    var existOperatorKeys = dynamicObject.Keys.Where(s => OperatorToTextDic.Keys.Any(s2 => s.Contains(s2))).ToList();
    //存在特殊字元變數的
    if (existOperatorKeys.Any())
    {
        //將符號替換成字母
        foreach (var s in existOperatorKeys)
        {
            var newKey = s;
            foreach (var s2 in OperatorToTextDic)
            {
                newKey = newKey.Replace(s2.Key.ToString(), s2.Value);
            }
            expression = expression.Replace(s, newKey);
        }
    }
    return expression;
}

PreParserInfixExpression 計算巢狀(),以及先行計算純數位，主要是在後面轉換為mongo語法的時候用到，讓純數位計算在記憶體中執行而不是資料庫中計算

/// <summary>
/// 預處理計算表示式
/// </summary>
/// <param name="expression">表示式</param>
/// <param name="dynamicObject">引數</param>
/// <param name="isCompile">是否是編譯</param>
/// <returns></returns>
public string PreParserInfixExpression(string expression, Dictionary<string, object> dynamicObject, bool isCompile = false)
{
    expression = expression.Trim();
    string pattern = @"((.*?))";
    Match match = Regex.Match(expression, pattern);
    if (match.Success && match.Groups.Count > 1)
    {
        var constText = match.Groups[0].Value;
        var constValue = match.Groups[1].Value;
        string numPattern = @"(([\s|0-9|+-*/|.]+))";
        //純數位計算 或者 不是編譯預約
        if (Regex.IsMatch(constText, numPattern) || !isCompile)
        {
            var evalValue = EvalNumber(constValue, dynamicObject);
            if (evalValue == null)
                return string.Empty;
            var replaceText = evalValue.ToString();
            expression = expression.Replace(constText, replaceText);
        }
        else if (isCompile)
        {
            //編譯計算
            var completeText = Compile(constValue, dynamicObject).ToString();
            //臨時引數Key
            var tempPramKey = "temp_" + Guid.NewGuid().ToString("n");
            dynamicObject.Add(tempPramKey, completeText);
            expression = expression.Replace(constText, tempPramKey);
        }
        else
        {
            return expression;
        }
        return PreParserInfixExpression(expression, dynamicObject, isCompile);
    }
    return expression;
}

ParserInfixExpression 表示式轉換核心程式碼

/// <summary>
/// 轉換表示式
/// </summary>
/// <param name="expression"></param>
/// <param name="dynamicObject"></param>
/// <param name="isComplete"></param>
/// <returns></returns>
public Queue<EvalItem> ParserInfixExpression(string expression, Dictionary<string, object> dynamicObject, bool isComplete = false)
{
    var queue = new Queue<EvalItem>();
    if (string.IsNullOrEmpty(expression))
        return queue;
    expression = PreReplaceOpratorToText(expression, dynamicObject);
    expression = PreParserInfixExpression(expression, dynamicObject, isComplete);
    if (string.IsNullOrEmpty(expression))
        return queue;
    var operatorStack = new Stack<OperatorChar>();

    int index = 0;
    int itemLength = 0;
    //當第一個字元為+或者-的時候
    char firstChar = expression[0];
    if (firstChar == AddOprator || firstChar == SubOperator)
    {
        expression = string.Concat("0", expression);
    }
    int expressionLength = expression.Length;
    using (var scanner = new StringReader(expression))
    {
        string operatorPreItem = string.Empty;
        while (scanner.Peek() > -1)
        {
            char currentChar = (char)scanner.Read();
            switch (currentChar)
            {
                case AddOprator:
                case SubOperator:
                case DivOperator:
                case MulOperator:
                case LBraceOperator:
                case RBraceOperator:
                    //直接把數位壓入到佇列中
                    operatorPreItem = expression.Substring(index, itemLength);
                    if (operatorPreItem != "")
                    {
                        var numberItem = new EvalItem(EItemType.Value, operatorPreItem);
                        queue.Enqueue(numberItem);
                    }
                    index = index + itemLength + 1;
                    itemLength = -1;
                    //當前操作符
                    var currentOperChar = new OperatorChar() { Operator = currentChar };
                    if (operatorStack.Count == 0)
                    {
                        operatorStack.Push(currentOperChar);
                        break;
                    }
                    //處理當前操作符與操作字元棧進出
                    var topOperator = operatorStack.Peek();
                    //若當前操作符為(或者棧頂元素為(則直接入棧
                    if (currentOperChar == LBraceOperatorChar || topOperator == LBraceOperatorChar)
                    {
                        operatorStack.Push(currentOperChar);
                        break;
                    }
                    //若當前操作符為),則棧頂元素順序輸出到佇列,至到棧頂元素(輸出為止,單(不進入佇列,它自己也不進入佇列
                    if (currentOperChar == RBraceOperatorChar)
                    {
                        while (operatorStack.Count > 0)
                        {
                            if (operatorStack.Peek() != LBraceOperatorChar)
                            {
                                var operatorItem = new EvalItem(EItemType.Operator, operatorStack.Pop().GetContent());
                                queue.Enqueue(operatorItem);
                            }
                            else
                            {
                                break;
                            }
                        }
                        if (operatorStack.Count > 0 && operatorStack.Peek() == RBraceOperatorChar)
                        {
                            operatorStack.Pop();
                        }
                        break;
                    }
                    //若棧頂元素優先順序高於當前元素，則棧頂元素輸出到佇列,當前元素入棧
                    if (topOperator.Level > currentOperChar.Level || topOperator.Level == currentOperChar.Level)
                    {
                        var topActualOperator = operatorStack.Pop();
                        var operatorItem = new EvalItem(EItemType.Operator, topActualOperator.GetContent());
                        queue.Enqueue(operatorItem);

                        while (operatorStack.Count > 0)
                        {
                            var tempTop = operatorStack.Peek();
                            if (tempTop.Level > currentOperChar.Level || tempTop.Level == currentOperChar.Level)
                            {
                                var topTemp = operatorStack.Pop();
                                var operatorTempItem = new EvalItem(EItemType.Operator, topTemp.GetContent());
                                queue.Enqueue(operatorTempItem);
                            }
                            else
                            {
                                break;
                            }
                        }
                        operatorStack.Push(currentOperChar);
                    }
                    //噹噹前元素小於棧頂元素的時候，當前元素直接入棧
                    else
                    {
                        operatorStack.Push(currentOperChar);
                    }
                    break;
                default:
                    break;
            }
            itemLength++;
        }
    }
    //剩餘無符號的字串
    if (index < expressionLength)
    {
        string lastNumber = expression.Substring(index, expressionLength - index);
        var lastNumberItem = new EvalItem(EItemType.Value, lastNumber);
        queue.Enqueue(lastNumberItem);
    }
    //彈出棧中所有操作符號
    if (operatorStack.Count > 0)
    {
        while (operatorStack.Count != 0)
        {
            var topOperator = operatorStack.Pop();
            var operatorItem = new EvalItem(EItemType.Operator, topOperator.GetContent());
            queue.Enqueue(operatorItem);
        }
    }
    return queue;
}

EvalDate 實現指定日期型別輸出

因專案需要，需要將當前日期，當前時間加入預設變數，並支援加入計算公式中，計算的結果也可以選擇是日期或者數值。

需要實現這個功能，需要先定義好，時間如何計算，我們將日期時間轉換成時間戳來進行轉換後參與計算，計算完成後再轉換成日期即可。

所以只需要在上面的數值計算包裹一層就可以得到日期的計算結果

EvalDate 核心程式碼

/// <summary>
/// 計算表示式的日期結果
/// </summary>
/// <param name="expression">表示式</param>
/// <param name="dynamicObject">動態物件</param>
/// <returns>計算的結果</returns>
public DateTime? EvalDate(string expression, Dictionary<string, object> dynamicObject)
{
    var dateNumValue = EvalNumber(expression, dynamicObject);
    if (dateNumValue == null)
        return null;
    if (long.TryParse(dateNumValue.ToString(), out long dateNum))
    {
        return JsTimeToDateTime(dateNum);
    }
    return null;
}

/// <summary>
/// 毫秒級時間戳轉成 DateTime
/// </summary>
/// <param name="unixTimestamp"></param>
/// <returns></returns>
private DateTime JsTimeToDateTime(long unixTimestamp)
{
    return DateTimeOffset.FromUnixTimeMilliseconds(unixTimestamp).LocalDateTime;
}

程式碼中的資料定義

其他資料定義 OperatorChar EvalItem EItemType CharExtension 可以檢視完整demo

後語

期間找了很多開源專案參考，需求的獨特性，最終是實現了功能

整個計算欄位的實現花了3周時間，終於是順利上線。

沉迷學習，無法自拔。