2020年9月17日星期四

简单实用算法——计算数学表达式

数学表达式的数值支持小数，符号只支持+ - * / ( )这几种。先将数学表达式的字符串（中缀表达式）转化为**后缀表达式**，然后计算后缀表达式的值。例：中缀表达式"9+(3-1)*3+10/2"转化为后缀表达式"9 3 1-3*+ 10 2/+"。

算法概述
算法代码(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

简单实用算法——计算数学表达式
竞争对手分析、吴佳、 初识亚马逊知识、 有钱有闲还爱亚马逊，这个国家值得跨境电商卖家深耕！、 德国VAT如何应对？Wish卖家看这篇就够了、 "被害妄想症"晚期，美国为啥总觉得自己吃了亏？、 消费税上调前，这三大爆单活动你会参加吗？、 亚马逊将下调22个类目佣金！7月15日起执行！、 出口电商冲刺黑五营销攻略分享会、 《我是传奇》第三集预告片、乐宝、 ideal、 发货到亚马逊FBA过程中遇到的问题及其解决办法！ 、 解读马来西亚三大本土电商平台成功之道、 教你怎么看广告数据、 电商大佬宣布关闭办公室！2020年这个趋势不可逆转、

星空资讯