逆波兰算法解析计算公式-白红宇

逆波兰算法解析计算公式

阅读量：6086 次

发布时间：2019-06-20

本文共 4490 字，大约阅读时间需要 14 分钟。

今天看书看到了逆波兰算法，想想以后可能会用到类似的算法功能，就写个demo

逆波兰表达式又叫做，我们常见的都是中缀表达式。例如：2+10*（3-1）

权重

我们根据运算符优先级去进栈出栈生成后缀表达式

此处用的字典存储的运算符权重

1         public static Dictionary
     
       dic = new Dictionary
      
       () { { "+", 1 }, { "-", 1 }, { "*", 2 }, { "/", 2 } };//权重

生成后缀表达式

把输入的公式拆解循环

遇到优先级较高的括号"()"此处办法是新添加一个内存去推算括号内的表达式（遇到中括号情况类似可以使用）

根据字符是无法分别元素是否是一个完整的数字所以此处取巧添加了一个bool类型状态去管理元素（数字元素结束添加空格分别元素）

1  　　　　//逆波兰公式（推算后缀表达式） 2         static string ClearUp(string str) 3         { 4             List
     
       list = new List
      
       (); 5             List
       
         list_tmp = new List
        
         (); 6             StringBuilder sb = new StringBuilder(); 7             StringBuilder sb_tmp = new StringBuilder(); 8             bool status = true;//状态标示（在元素前添加空格标示完整元素） 9             foreach (char item in str)10             {11                 switch (item)12                 {13                     case '+':14                         status = false;15                         Fun_Formula(item, list, sb, status);16                         break;17                     case '-':18                         status = false;19                         Fun_Formula(item, list, sb, status);20                         break;21                     case '*':22                         status = false;23                         Fun_Formula(item, list, sb, status);24                         break;25                     case '/':26                         status = false;27                         Fun_Formula(item, list, sb, status);28                         break;29                     case '('://使用临时栈保存原有数据（开辟新栈计算片段）30                         status = false;31                         for (int i = 0; i < list.Count; i++)32                         {33                             list_tmp.Add(list[i]);34                         }35                         list.Clear();36                         sb_tmp.Append(sb.ToString());37                         sb.Clear();38                         break;39                     case ')'://结束新内存（赋值给主栈）40                         status = false;41                         for (int i = list.Count - 1; i >= 0; i--)42                         {43                             sb.Append(" " + list[i]);44                             list.RemoveAt(i);45                         }46                         for (int i = list_tmp.Count - 1; i >= 0; i--)47                         {48                             list.Add(list_tmp[i]);49                         }50                         list_tmp.Clear();51                         sb_tmp.Append(sb.ToString());52                         sb.Clear();53                         sb.Append(sb_tmp.ToString());54                         sb_tmp.Clear();55                         break;56                     default:57                         status = true;58                         sb.Append(item);59                         break;60                 }61             }62             for (int i = list.Count - 1; i >= 0; i--)//计算结束栈内元素依次出栈63             {64                 sb.Append(" " + list[i]);65             }66             return sb.ToString();67         }

计算后缀表达式

循环出栈计算运算符之前的2个元素，计算完成值进栈参与下次进栈

1   　　　　//根据后缀表达式计算（以空格区分元素） 2         static string Calculate(string str) 3 { 4 List
     
       list = new List
      
       (); 5 double result; 6 foreach (string item in str.Split(' ')) 7 { 8 switch (item) 9 { 10 case "+": 11 result = double.Parse(list[list.Count - 2]) + double.Parse(list[list.Count - 1]); 12 list.RemoveAt(list.Count - 1); 13 list.RemoveAt(list.Count - 1); 14 list.Add(result.ToString()); 15 break; 16 case "-": 17 result = double.Parse(list[list.Count - 2]) - double.Parse(list[list.Count - 1]); 18 list.RemoveAt(list.Count - 1); 19 list.RemoveAt(list.Count - 1); 20 list.Add(result.ToString()); 21 break; 22 case "*": 23 result = double.Parse(list[list.Count - 2]) * double.Parse(list[list.Count - 1]); 24 list.RemoveAt(list.Count - 1); 25 list.RemoveAt(list.Count - 1); 26 list.Add(result.ToString()); 27 break; 28 case "/": 29 result = double.Parse(list[list.Count - 2]) / double.Parse(list[list.Count - 1]); 30 list.RemoveAt(list.Count - 1); 31 list.RemoveAt(list.Count - 1); 32 list.Add(result.ToString()); 33 break; 34 default: 35 list.Add(item.ToString()); 36 break; 37 } 38 } 39 return list[0].ToString(); 40 }