目錄

• 演算法概述
• 演算法代碼(C#)
• 演算法實作
• 參考資料

演算法概述

變數定義： str-數學運算式
注：數學運算式的數值支持小數，符號只支持+ - * / ( )這幾種，

計算原理：：先將數學運算式的字串（中綴運算式）轉化為后綴運算式，然后計算后綴運算式的值，
注：為了運算結果的精度，運算程序中統一使用decimal型別的資料，

例：輸入運算式"10*1.1/(2+8)+1.1+2.2-4.3"，輸出結果“0.1”，

演算法代碼(C#)

代碼如下：

//測驗演算法
class Program
{
    static void Main(string[] args)
    {
        string str = "10*1.1/(2+8)+1.1+2.2-4.3";
        decimal res = Calculator.Calculate(str);
        Console.WriteLine(str+"="+res);
        Console.ReadLine();
    }        
}

/// <summary>
/// 計算數學運算式，基于后綴運算式的實作，可使用 + - * / ( ) 運算子
/// </summary>
class Calculator 
{
    /// <summary>
    /// 計算數學運算式的值
    /// </summary>
    /// <param name="str">數學運算式</param>
    /// <returns></returns>
    public static decimal Calculate(string str)
    {            
        try
        {
            Queue<string> queue = CreateRPN(str);
            decimal res = ParseRPN(queue);
            return res;
        }
        catch (OverflowException)
        {
            throw new Exception("資料過大導致計算溢位");
        }
        catch (Exception)
        {
            throw new Exception("無法計算錯誤的運算式");
        }
            
    }

    //生成后綴運算式
    private static Queue<string> CreateRPN(string str)
    {
        //臨時存盤+ - * / ( 符號的堆疊
        Stack<char> stack = new Stack<char>();
        //存盤后綴運算式的佇列
        Queue<string> queue = new Queue<string>();
        for (int i = 0; i < str.Length; )
        {
            //如果是空格直接跳過
            if (str[i] == ' ')
            {
                i++;
                continue;
            }
            else if ((str[i] >= '0' && str[i] <= '9') || (str[i] == '.'))
            {
                //當前數
                decimal cur = 0;
                //小數標識
                bool isDecimal = false;
                //小數位數
                int num = 0;
                //特別要注意i < s.length這個條件
                while (i < str.Length && ((str[i] >= '0' && str[i] <= '9') || (str[i] == '.')))
                {
                    if (str[i] == '.')
                    {
                        isDecimal = true;
                    }
                    else
                    {
                        if (!isDecimal)
                        {
                            cur = cur * 10 + str[i] - '0';
                        }
                        else
                        {
                            num++;
                            cur = cur + ((decimal)(str[i] - '0')) / (decimal)(Math.Pow(10, num));
                        }
                    }
                    i++;
                }
                queue.Enqueue(cur.ToString());
            }
            else if (str[i] == ')')
            {
                //如果是 " )"那么需要彈出堆疊中的運算子號，并且把它加入到后綴運算式的佇列中
                //一直到遇到符號堆疊中的 " ( " 為止
                while (stack.Count != 0 && stack.Peek() != '(')
                {
                    queue.Enqueue(stack.Pop() + "");
                }
                stack.Pop();
                i++;
            }
            else
            {
                //可能是 +  -  *  / 這些符號或者是左括號
                //這個時候需要判斷符號堆疊中的堆疊頂元素與當前遍歷到的字符的優先級的問題
                while (stack.Count != 0 && Compare(stack.Peek(), str[i]) < 0)
                {
                    queue.Enqueue(stack.Pop() + "");
                }
                stack.Push(str[i]);
                i++;
            }
        }
        while (stack.Count != 0)
        {
            queue.Enqueue(stack.Pop() + "");
        }
        return queue;
    }

    //處理符號優先級
    private static int Compare(char peek, char c)
    {
        if (peek == '(' || c == '(') return 1;
        if (c == '+' || c == '-') return -1;
        if (c == '*' && (peek == '*' || peek == '/')) return -1;
        if (c == '/' && (peek == '*' || peek == '/')) return -1;
        return 1;
    }

    //決議后綴運算式
    private static decimal ParseRPN(Queue<string> queue)
    {
        //結果堆疊
        Stack<decimal> res = new Stack<decimal>();
        while (queue.Count != 0)
        {
            String t = queue.Dequeue();
            if (t.Equals("+") || t.Equals("-") || t.Equals("*") || t.Equals("/"))
            {
                decimal a = res.Pop();
                decimal b = res.Pop();
                decimal result = Calculate(b, a, t);
                res.Push(result);
            }
            else
            {
                res.Push(decimal.Parse(t));
            }
        }
        return res.Pop();
    }

    //基本運算單元
    private static decimal Calculate(decimal a, decimal b, String t)
    {
        //計算
        if (t.Equals("+"))
        {
            return a + b;
        }
        else if (t.Equals("-"))
        {
            return a - b;
        }
        else if (t.Equals("*"))
        {
            return a * b;
        }
        else
        {
            return a / b;
        }
    }
}

注：上面的代碼簡單擴展一下即可支持更復雜的運算子

演算法實作

中綴運算式轉化為后綴運算式規則：從左到右遍歷中綴運算式的每個數字和符號，若是數字就輸出，即成為后綴運算式的一部分；若是符號，則判斷其與堆疊頂符號的優先級，是右括號或優先級低于找頂符號（乘除優先加減）則堆疊頂元素依次出找并輸出，并將當前符號進堆疊，一直到最終輸出后綴運算式為止，

例：中綴運算式“9+(3-1)3+10/2”轉化為后綴運算式“9 3 1-3+ 10 2/+”，

后綴運算式的計算程序規則：從左到右遍歷運算式的每個數字和符號，遇到是數字就進堆疊，遇到是符號，就將處于堆疊頂兩個數字出堆疊，進行運算，運算結果進堆疊，一直到最侄訓得結果，

參考資料

堆疊實作計算數學運算式——CSDN
接觸后綴運算式（逆波蘭表示法）——Veda
將中綴運算式轉化為后綴運算式——Veda
圖解后綴運算式的計算程序——Veda

標籤：C#

上一篇：求一個正則運算式！

下一篇：EFCore的事務和分布式事務的使用