表达式求值

前两天翻看《数据结构》，看到有个表达式求值的东西比较有意思。于是乎就用c#代码实现了下。倒腾了半天 总算能工作了。 看到博客园的前辈们也写过好多类似的例子 献丑了。程序设计语言中都有计算表达式的问题，这是语言编译中的典型问题。看到博客园的其他帖子好多都是说什么后缀表达式 什么的。我这个代码比较短 但是基础功能是完全实现了的。

《数据结构》第3章63 页 是讲堆栈。就是stack 这个鸟玩意儿 。以前存数据 都是用list 类似于链表 。谁用过这个啊 有什么用。没什么用 就是一种数据结构。表达式求值这当中利用了一个重要特性 那就是堆栈的先进后出。 不论是我们的高级程序语言 还是表达式 ，他们都有一个重要的特性就是 大括号包小括号 括号当中包括号。并且有左括号就会有右括号 是相互对称的 ，其实要说的话 这个是一种递归结构。 不管怎么说 遇左括号入栈 遇右括号出栈 ，堆栈天生就有一种处理这种问题的能力，并且还让条理更清晰。

我这段代码的大概原理就是书上讲的那样：

先给个运算符优先级表

1 char[,] compareTable = new char[7, 7]{2             {'>','>','<','<','<','>','>'},3             {'>','>','<','<','<','>','>'},4             {'>','>','>','>','<','>','>'},5             {'>','>','>','>','<','>','>'},6             {'<','<','<','<','<','=','x'},7             {'>','>','>','>','x','>','>'},8             {'<','<','<','<','<','x','='}9             };

横着竖着7行7列 依次对应+-*/()# 行数为第一个变量 列数为第二个变量 ，比如+与*为 compare[0,2] 是小于符号 ，+号优先级小于*然后是规则：从左往右扫描，遇操作数进Operator栈 遇操作符进行下面的逻辑1若栈顶运算符优先级低于刚读入的运算符 则让刚读入的运算符进入operator栈2若栈顶运算符的优先级高于刚读入的运算符则将栈顶运算符退栈 ，同时将操作数栈operand退栈两次 让他们进行运算 运算结果推入operator栈3若优先级相同 说明左右括号相遇 只需将栈顶运算符退栈即可当栈顶操作符和刚读入操作符均为#时 说明表达式结束

就这样如此往复 遇到一个小的计算单位就会自动求值并消除操作数和操作符 然后又让求出的值和其他值进行运算 如此往复以小到大都求出整个表达式的值。

  1 public char compareOper(char oPR1, char opr2)  2         {  3             char[,] compareTable = new char[7, 7]{  4             {'>','>','<','<','<','>','>'},  5             {'>','>','<','<','<','>','>'},  6             {'>','>','>','>','<','>','>'},  7             {'>','>','>','>','<','>','>'},  8             {'<','<','<','<','<','=','x'},  9             {'>','>','>','>','x','>','>'}, 10             {'<','<','<','<','<','x','='} 11             }; 12  13             int opr1Indx = 0; 14             switch (opr1) 15             { 16                 case '+': 17                     opr1Indx = 0; 18                     break; 19                 case '-': 20                     opr1Indx = 1; 21                     break; 22                 case '*': 23                     opr1Indx = 2; 24                     break; 25                 case '/': 26                     opr1Indx = 3; 27                     break; 28                 case '(': 29                     opr1Indx = 4; 30                     break; 31                 case ')': 32                     opr1Indx = 5; 33                     break; 34                 case '#': 35                     opr1Indx = 6; 36                     break; 37                 default: 38                     break; 39             } 40             int opr2Indx = 0; 41             switch (opr2) 42             { 43                 case '+': 44                     opr2Indx = 0; 45                     break; 46                 case '-': 47                     opr2Indx = 1; 48                     break; 49                 case '*': 50                     opr2Indx = 2; 51                     break; 52                 case '/': 53                     opr2Indx = 3; 54                     break; 55                 case '(': 56                     opr2Indx = 4; 57                     break; 58                 case ')': 59                     opr2Indx = 5; 60                     break; 61                 case '#': 62                     opr2Indx = 6; 63                     break; 64                 default: 65                     break; 66             } 67  68             return compareTable[opr1Indx, opr2Indx]; 69         } 70         public int calc(int num1, int num2, char opr) 71         { 72             switch (opr) 73             { 74                 case '+': 75                     return num1 + num2; 76                     break; 77                 case '-': 78                     return num1 - num2; 79                     break; 80                 case '*': 81                     return num1 * num2; 82                     break; 83                 case '/': 84                     return num1 / num2; 85                     break; 86  87                 default: 88                     break; 89             } 90             return 0; 91         } 92         private void button1_Click(object sender, EventArgs e) 93         { 94             Stack<int> operand = new Stack<int>(); 95             Stack<char> opera = new Stack<char>(); 96             opera.Push('#'); 97  98             string exp = textBox1.Text; 99 100             Regex numVali = new Regex(@"/d");101 102             //MessageBox.Show(numVali.IsMatch("6").ToString());103 104             for (int i = 0; i < exp.Length; i++)105             {106                 if (numVali.IsMatch(exp[i] + "") == true || exp[i] == ' ')//数字107                 {108                     string numTmp = exp[i] + "";109                     int nextNumIndx = 1;110                     char nextNum = exp[i + (nextNumIndx)];111                     nextNumIndx++;112                     while (numVali.IsMatch(nextNum + "") == true || nextNum == ' ')113                     {114                         numTmp += nextNum;115                         if (i + (nextNumIndx) < exp.Length)116                         {117                             nextNum = exp[i + (nextNumIndx)];118                             nextNumIndx++;119                         }120                         else121                             break;122                     }123                     operand.Push(int.Parse(numTmp.Replace(" ", "")));124                     i = i + nextNumIndx - 1 - 1;125 126                 }127                 else//操作符128                 {129 132                     switch (compareOper(opera.Peek(), exp[i]))133                     {134                         case '<':135                             opera.Push(exp[i]);136                             break;137                         case '=':138                             opera.Pop();139                             break;140                         case '>':141 142                             int b = operand.Pop();143                             int a = operand.Pop();144                             operand.Push(calc(a, b, opera.Pop()));145 146  147                             if (compareOper(opera.Peek(), exp[i]) == '=')148                             {149                                 opera.Pop();150                             }151                             else if (compareOper(opera.Peek(), exp[i]) == '>')152                             {153                                  b = operand.Pop();154                                  a = operand.Pop();155                                 operand.Push(calc(a, b, opera.Pop()));156                                 //opera.Push(exp[i]);157 158                                 if (compareOper(opera.Peek(), exp[i]) == '=')159                                 {160                                     opera.Pop();161                                 }162                                 else if (compareOper(opera.Peek(), exp[i]) == '>')163                                 {164                                     b = operand.Pop();165                                     a = operand.Pop();166                                     operand.Push(calc(a, b, opera.Pop()));167                                     opera.Push(exp[i]);168                                 }169                                 else if (compareOper(opera.Peek(), exp[i]) == '<')170                                     opera.Push(exp[i]);171                             }172                             else if (compareOper(opera.Peek(), exp[i]) == '<')173                                 opera.Push(exp[i]);174                             break;175                         default:176                             break;177                     }178                     if (exp[i] == '#')179                         break;180                 }181             }182             MessageBox.Show(string.Forma