引言
最近做一個配置的功能，需求是該配置項跟另一個整形配置項關聯，具有一定的函式關系，例如有一個配置項是值為 N ，則另一配置 F 項滿足函式關系\(F=2/(N+1)\)，這個函式關系是客戶手動輸入，只需要簡單的四則運算，所以我們要做的就是判斷四則運算運算式是否有效，且給定 N 的值，算出運算式的值，
如何快速判斷一個四則運算公式字串是否符合規則，且根據給定值計算出該公式的值？
雙堆疊實作
實際上編譯器就是利用了雙堆疊實作了的運算式求值，其中一個堆疊用來保存運算元，另一個堆疊用來保存運算子，
從左向右遍歷運算式，當遇到數字時，就將其直接壓入運算元堆疊；當遇到運算子時，就將其與運算子堆疊的堆疊頂元素比較，
如果遇到的運算子比運算子堆疊頂的元素的優先級高，就將這個運算子壓入堆疊；
如果遇到的運算子比運算子堆疊頂的元素的優先級低或兩者相同，就從運算子堆疊頂取出運算子，在從運算元堆疊頂取兩個運算元，然后進行計算，并把計算的得到的結果壓入運算元堆疊，繼續比較這個運算子與運算子堆疊頂的元素；
下圖表示一個簡單四則運算運算式 3+5*8-6的計算程序：
代碼實作可以大概簡化可以分為以下步驟：
-
定義運算子堆疊
operatorStack和運算元堆疊operandStack， -
從左至右掃描運算式,遇到運算元時,直接將其推入運算元堆疊
operandStack， -
遇到運算子時,比較其與運算子堆疊頂部運算子的優先級:
-
如果該運算子的優先級高于或等于運算子堆疊頂部運算子,則將該運算子直接入堆疊
operatorStack， -
如果該運算子的優先級低于運算子堆疊頂部運算子,則將運算子堆疊頂部的運算子出堆疊,從運算元堆疊中彈出兩個運算元,計算結果后再入堆疊
operandStack,重復此步驟直到運算子堆疊為慷訓遇到優先級高于或等于該運算子的堆疊頂運算子為止，
-
-
遇到括號時:
-
如果是左括號“(”,則直接入堆疊
operatorStack， -
如果是右括號“)”,則將運算子堆疊堆疊頂的運算子出堆疊,從運算元堆疊中彈出兩個運算元計算結果,重復此步驟直到遇到左括號為止,并將這一對括號從運算子堆疊中移除，
-
-
重復步驟3和4,直到運算式的最右端，
-
將運算子堆疊中剩余的所有運算子依次出堆疊,從運算元堆疊中彈出兩個運算元,計算結果后入堆疊operandStack，
-
運算元堆疊最終只剩一個運算元,這就是運算式的計算結果，
具體實作代碼如下：
class ExpressionEvaluator
{
static Dictionary<char, int> PrecedenceDic = new Dictionary<char, int> {
{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}
};
static Dictionary<char, Func<int, int, int>> OperatorsDic = new Dictionary<char, Func<int, int, int>> {
{'+', (a, b) => a + b },
{'-', (a, b) => a - b },
{'*', (a, b) => a * b },
{'/', (a, b) => a / b },
{'^', (a, b) => (int)Math.Pow(a, b)}
};
public static bool EvaluateExpression(string expression, out double result)
{
result = 0;
try
{
// 使用正則運算式驗證四則運算運算式的有效性
string pattern = @"^[-+*/^() x\d\s]+$";
if (!Regex.IsMatch(expression, pattern))
{
return false;
}
//運算子堆疊
Stack<char> operatorStack = new Stack<char>();
//運算元堆疊
Stack<int> operandStack = new Stack<int>();
for (int i = 0; i < expression.Length; i++)
{
char c = expression[i];
if (c == ' ') continue;
if (char.IsDigit(c))
{
//獲取運算元
int operand = 0;
while (i < expression.Length && char.IsDigit(expression[i]))
{
operand = operand * 10 + (expression[i++] - '0');
}
i--;
operandStack.Push(operand);
}
else if (OperatorsDic.ContainsKey(c))
{
while (operatorStack.Count > 0 &&
OperatorsDic[c] != null && operatorStack.Peek() != '(' &&
PrecedenceDic[operatorStack.Peek()] >= PrecedenceDic[c])
{
int b = operandStack.Pop();
int a = operandStack.Pop();
operandStack.Push(OperatorsDic[operatorStack.Pop()](a, b));
}
operatorStack.Push(c);
}
else if (c == '(')
{
operatorStack.Push(c);
}
else if (c == ')')
{
while (operatorStack.Peek() != '(')
{
int b = operandStack.Pop();
int a = operandStack.Pop();
operandStack.Push(OperatorsDic[operatorStack.Pop()](a, b));
}
operatorStack.Pop();
}
}
while (operatorStack.Count > 0)
{
int b = operandStack.Pop();
int a = operandStack.Pop();
operandStack.Push(OperatorsDic[operatorStack.Pop()](a, b));
}
result = operandStack.Pop();
return true;
}
catch (Exception)
{
return false;
}
}
}
那接下來測驗一下代碼，因為代碼內只做了整形的計算，所以運算式也只用整形，
官方API
實際上微軟官方在 System.Data 庫中 DataTable.Compute(String, String)方法實作了計算運算式，代碼如下
using System;
using System.Data;
using System.Text.RegularExpressions;
public class ArithmeticExpressionEvaluator
{
public static bool IsArithmeticExpression(int arg, string str, out double result)
{
result = 0;
// 驗證字串是否包含有效的四則運算運算式
if (!IsValidArithmeticExpression(str) || !str.ToLower().Contains("x".ToLower()))
{
return false;
}
// 將字串中的變數x替換為傳入的整數arg
string expression = str.Replace("x", arg.ToString());
// 計算并回傳運算式的值
try
{
return double.TryParse(new DataTable().Compute(expression, "").ToString(), out result);
}
catch
{
return false;
}
}
private static bool IsValidArithmeticExpression(string str)
{
// 使用正則運算式驗證四則運算運算式的有效性
string pattern = @"^[-+*/() x\d\s]+$";
return Regex.IsMatch(str, pattern);
}
}
class Program
{
public static void Main()
{
while (true)
{
string expression = Console.ReadLine();
string arg = Console.ReadLine();
if (ArithmeticExpressionEvaluator.IsArithmeticExpression(int.Parse(arg), expression, out double result))
{
Console.WriteLine($"The result of the arithmetic expression is: {result}");
}
else
{
Console.WriteLine("The input string is not a valid arithmetic expression.");
}
}
}
}
測驗結果：
總結
剛開始拿到這個需求還是有點頭疼的，想了很久的方案，突然想到之前看資料結構的書的時候，提到過堆疊在運算式求值中的應用，翻書看了一下，還是被這個實作方案驚艷到了，所以，還是需要多讀多看多思考，才能在面對各種需求游刃有余，加油~
作者： Peter.Pan
出處： https://www.cnblogs.com/pandefu/>
關于作者：.Net Framework，.Net Core ,WindowsForm,WPF ,控制元件庫，多執行緒
本文著作權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段宣告，且在文章頁面明顯位置給出 原文鏈接,否則保留追究法律責任的權利， 如有問題， 可郵件咨詢，
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/557090.html
標籤：C#
下一篇：返回列表