引言
最近做一個配置的功能，需求是該配置項跟另一個整形配置項關聯(lián)，具有一定的函數(shù)關系，例如有一個配置項是值為 N ，則另一配置 F 項滿足函數(shù)關系\(F=2/(N+1)\)。這個函數(shù)關系是客戶手動輸入，只需要簡單的四則運算，所以我們要做的就是判斷四則運算表達式是否有效，且給定 N 的值，算出表達式的值。
如何快速判斷一個四則運算公式字符串是否符合規(guī)則，且根據(jù)給定值計算出該公式的值？
雙棧實現(xiàn)
實際上編譯器就是利用了雙棧實現(xiàn)了的表達式求值，其中一個棧用來保存操作數(shù)，另一個棧用來保存運算符。
從左向右遍歷表達式，當遇到數(shù)字時，就將其直接壓入操作數(shù)棧；當遇到運算符時，就將其與運算符棧的棧頂元素比較。
如果遇到的運算符比運算符棧頂?shù)脑氐膬?yōu)先級高，就將這個運算符壓入棧；
如果遇到的運算符比運算符棧頂?shù)脑氐膬?yōu)先級低或兩者相同，就從運算符棧頂取出運算符，在從操作數(shù)棧頂取兩個操作數(shù)，然后進行計算，并把計算的得到的結果壓入操作數(shù)棧，繼續(xù)比較這個運算符與運算符棧頂?shù)脑兀?/p>
下圖表示一個簡單四則運算表達式 3+5*8-6的計算過程：
代碼實現(xiàn)可以大概簡化可以分為以下步驟：
-
定義運算符棧
operatorStack和操作數(shù)棧operandStack。 -
從左至右掃描表達式,遇到操作數(shù)時,直接將其推入操作數(shù)棧
operandStack。 -
遇到運算符時,比較其與運算符棧頂部運算符的優(yōu)先級:
-
如果該運算符的優(yōu)先級高于或等于運算符棧頂部運算符,則將該運算符直接入棧
operatorStack。 -
如果該運算符的優(yōu)先級低于運算符棧頂部運算符,則將運算符棧頂部的運算符出棧,從操作數(shù)棧中彈出兩個操作數(shù),計算結果后再入棧
operandStack,重復此步驟直到運算符棧為空或遇到優(yōu)先級高于或等于該運算符的棧頂運算符為止。
-
-
遇到括號時:
-
如果是左括號“(”,則直接入棧
operatorStack。 -
如果是右括號“)”,則將運算符棧棧頂?shù)倪\算符出棧,從操作數(shù)棧中彈出兩個操作數(shù)計算結果,重復此步驟直到遇到左括號為止,并將這一對括號從運算符棧中移除。
-
-
重復步驟3和4,直到表達式的最右端。
-
將運算符棧中剩余的所有運算符依次出棧,從操作數(shù)棧中彈出兩個操作數(shù),計算結果后入棧operandStack。
-
操作數(shù)棧最終只剩一個操作數(shù),這就是表達式的計算結果。
具體實現(xiàn)代碼如下：
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>();
//操作數(shù)棧
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))
{
//獲取操作數(shù)
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)方法實現(xiàn)了計算表達式，代碼如下
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替換為傳入的整數(shù)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.");
}
}
}
}
測試結果：文章來源：http://www.zghlxwxcb.cn/news/detail-548556.html
總結
剛開始拿到這個需求還是有點頭疼的，想了很久的方案，突然想到之前看數(shù)據(jù)結構的書的時候，提到過棧在表達式求值中的應用，翻書看了一下，還是被這個實現(xiàn)方案驚艷到了，所以，還是需要多讀多看多思考，才能在面對各種需求游刃有余，加油~文章來源地址http://www.zghlxwxcb.cn/news/detail-548556.html
到了這里，關于編碼技巧 --- 如何實現(xiàn)字符串運算表達式的計算的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
