- A+
所属分类：.NET技术
算法概述
变量定义： 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
