表達(dá)式求值

前兩天翻看《數(shù)據(jù)結(jié)構(gòu)》，看到有個(gè)表達(dá)式求值的東西比較有意思。于是乎就用c#代碼實(shí)現(xiàn)了下。倒騰了半天 總算能工作了。 看到博客園的前輩們也寫過好多類似的例子 獻(xiàn)丑了。程序設(shè)計(jì)語(yǔ)言中都有計(jì)算表達(dá)式的問題，這是語(yǔ)言編譯中的典型問題。看到博客園的其他帖子好多都是說(shuō)什么后綴表達(dá)式 什么的。我這個(gè)代碼比較短 但是基礎(chǔ)功能是完全實(shí)現(xiàn)了的。

《數(shù)據(jù)結(jié)構(gòu)》第3章63 頁(yè) 是講堆棧。就是stack 這個(gè)鳥玩意兒 。以前存數(shù)據(jù) 都是用list 類似于鏈表 。誰(shuí)用過這個(gè)啊 有什么用。沒什么用 就是一種數(shù)據(jù)結(jié)構(gòu)。表達(dá)式求值這當(dāng)中利用了一個(gè)重要特性 那就是堆棧的先進(jìn)后出。 不論是我們的高級(jí)程序語(yǔ)言 還是表達(dá)式 ，他們都有一個(gè)重要的特性就是 大括號(hào)包小括號(hào) 括號(hào)當(dāng)中包括號(hào)。并且有左括號(hào)就會(huì)有右括號(hào) 是相互對(duì)稱的 ，其實(shí)要說(shuō)的話 這個(gè)是一種遞歸結(jié)構(gòu)。 不管怎么說(shuō) 遇左括號(hào)入棧 遇右括號(hào)出棧 ，堆棧天生就有一種處理這種問題的能力，并且還讓條理更清晰。

我這段代碼的大概原理就是書上講的那樣：

先給個(gè)運(yùn)算符優(yōu)先級(jí)表

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

橫著豎著7行7列 依次對(duì)應(yīng)+-*/()# 行數(shù)為第一個(gè)變量 列數(shù)為第二個(gè)變量 ，比如+與*為 compare[0,2] 是小于符號(hào) ，+號(hào)優(yōu)先級(jí)小于*然后是規(guī)則：從左往右掃描，遇操作數(shù)進(jìn)Operator棧 遇操作符進(jìn)行下面的邏輯1若棧頂運(yùn)算符優(yōu)先級(jí)低于剛讀入的運(yùn)算符 則讓剛讀入的運(yùn)算符進(jìn)入operator棧2若棧頂運(yùn)算符的優(yōu)先級(jí)高于剛讀入的運(yùn)算符則將棧頂運(yùn)算符退棧 ，同時(shí)將操作數(shù)棧operand退棧兩次 讓他們進(jìn)行運(yùn)算 運(yùn)算結(jié)果推入operator棧3若優(yōu)先級(jí)相同 說(shuō)明左右括號(hào)相遇 只需將棧頂運(yùn)算符退棧即可當(dāng)棧頂操作符和剛讀入操作符均為#時(shí) 說(shuō)明表達(dá)式結(jié)束

就這樣如此往復(fù) 遇到一個(gè)小的計(jì)算單位就會(huì)自動(dòng)求值并消除操作數(shù)和操作符 然后又讓求出的值和其他值進(jìn)行運(yùn)算 如此往復(fù)以小到大都求出整個(gè)表達(dá)式的值。

  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] == ' ')//數(shù)字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