前兩天翻看《數據結構》，看到有個表達式求值的東西比較有意思。於是乎就用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 else
121 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.Format("結果是{0}", operand.Peek()));
183 }
就這樣了 ，親測 可用。暫時只能計算整數哈，一個正確的輸入 應該像這樣:（3+2）*4# 。以井號結尾
