## 引言 最近做一個配置的功能，需求是該配置項跟另一個整形配置項關聯，具有一定的函數關係，例如有一個配置項是值為 `N` ，則另一配置 `F` 項滿足函數關係$F=2/(N+1)$。這個函數關係是客戶手動輸入，只需要簡單的四則運算，所以我們要做的就是判斷四則運算表達式是否有效，且給定 `N` 的值 ...
引言
最近做一個配置的功能，需求是該配置項跟另一個整形配置項關聯，具有一定的函數關係，例如有一個配置項是值為 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.");
}
}
}
}
測試結果：
總結
剛開始拿到這個需求還是有點頭疼的，想了很久的方案，突然想到之前看數據結構的書的時候，提到過棧在表達式求值中的應用，翻書看了一下，還是被這個實現方案驚艷到了，所以，還是需要多讀多看多思考，才能在面對各種需求游刃有餘，加油~
作者： Niuery Daily
出處： https://www.cnblogs.com/pandefu/>
關於作者：.Net Framework，.Net Core ,WindowsForm,WPF ,控制項庫，多線程
本文版權歸作者所有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出 原文鏈接,否則保留追究法律責任的權利。 如有問題， 可郵件咨詢。
