编码技巧 — 如何实现字符串运算表达式的计算

引言

最近做一个配置的功能，需求是该配置项跟另一个整形配置项关联，具有一定的函数关系，例如有一个配置项是值为 N ，则另一配置 F 项满足函数关系(F=2/(N+1))。这个函数关系是客户手动输入，只需要简单的四则运算，所以我们要做的就是判断四则运算表达式是否有效，且给定 N 的值，算出表达式的值。

如何快速判断一个四则运算公式字符串是否符合规则，且根据给定值计算出该公式的值？

双栈实现

实际上编译器就是利用了双栈实现了的表达式求值，其中一个栈用来保存操作数，另一个栈用来保存运算符。

从左向右遍历表达式，当遇到数字时，就将其直接压入操作数栈；当遇到运算符时，就将其与运算符栈的栈顶元素比较。

如果遇到的运算符比运算符栈顶的元素的优先级高，就将这个运算符压入栈；

如果遇到的运算符比运算符栈顶的元素的优先级低或两者相同，就从运算符栈顶取出运算符，在从操作数栈顶取两个操作数，然后进行计算，并把计算的得到的结果压入操作数栈，继续比较这个运算符与运算符栈顶的元素；

下图表示一个简单四则运算表达式 3+5*8-6的计算过程：

代码实现可以大概简化可以分为以下步骤：

1. 定义运算符栈 operatorStack 和操作数栈 operandStack 。

2. 从左至右扫描表达式,遇到操作数时,直接将其推入操作数栈 operandStack 。

3. 遇到运算符时,比较其与运算符栈顶部运算符的优先级:

   • 如果该运算符的优先级高于或等于运算符栈顶部运算符,则将该运算符直接入栈 operatorStack 。

   • 如果该运算符的优先级低于运算符栈顶部运算符,则将运算符栈顶部的运算符出栈,从操作数栈中弹出两个操作数,计算结果后再入栈 operandStack ,重复此步骤直到运算符栈为空或遇到优先级高于或等于该运算符的栈顶运算符为止。

4. 遇到括号时:

   • 如果是左括号“(”,则直接入栈 operatorStack 。

   • 如果是右括号“)”,则将运算符栈栈顶的运算符出栈,从操作数栈中弹出两个操作数计算结果,重复此步骤直到遇到左括号为止,并将这一对括号从运算符栈中移除。

5. 重复步骤3和4,直到表达式的最右端。

6. 将运算符栈中剩余的所有运算符依次出栈,从操作数栈中弹出两个操作数,计算结果后入栈operandStack。

7. 操作数栈最终只剩一个操作数,这就是表达式的计算结果。

具体实现代码如下：

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 = @"^[-+*/^() xds]+$";              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 = @"^[-+*/() xds]+$";         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.");             }         }     } } 

测试结果：

总结

刚开始拿到这个需求还是有点头疼的，想了很久的方案，突然想到之前看数据结构的书的时候，提到过栈在表达式求值中的应用，翻书看了一下，还是被这个实现方案惊艳到了，所以，还是需要多读多看多思考，才能在面对各种需求游刃有余，加油~