為了全面檢查腳本存在的BUG,必須要寫一個相對復雜的程序測試腳本,應VCZH朋友的建議,我寫了這個表達式計算器,400多行代碼...我想沒人會用我這個腳本寫更長的程序了,對吧？因此,調試通過的同時也就意味著測試工作的暫告一段落，接下來得改進內存管理的一些問題．
鑒于上篇文章被管理員移除的教訓，我決定稍微介紹一下表達式計算的方法，當然都是些比較簡單的東西，考慮這樣一個表達式：2 + (3 + 2) + 4 * 3，結果等于多少？你很和諧的大腦應該能很快就算出一個數字:19,是的，對了，那么你是怎么計算出來的呢？你的大腦思考過程大概就是：一眼看到括號，計算3+2=5,再計算2+5=7,看到乘號，計算4*3=12,最后相加=19．就是說，你的大腦把這個表達式分成了三項，2,(3+2),4*3，分別計算出值再按順序相加得到結果，用電腦計算表達式的處理過程也類似，首先我們根據優先級把表達式分為三個層次：表達式、項、因子，每個加減號左右的操作數為項，每個乘除號左右的操作數為因子，在上面那個表達式中，項為2，(3 + 2)，4 * 3，因子為2,(3+2),4,3,所以，我們的處理順序是：計算因子的值－計算項的值－計算表達式的值，這可以通過遞歸實現，想象我們有這么幾個函數：parseExpr,parseTemp,parseFactor,對上面那個式子，首先ParseFactor處理因子2，處理完后返回到ParseTemp再返回到parseExpr，得到正確的操作符+,接著處理第二個項(3 + 2)，因為是個表達式，所以到因子級別時遞歸調用parseExpr．．．一直到達表達式的末尾，為了方便處理，在編譯時，通常會把這樣的表達式翻譯為后綴表達式，2 + (3 + 2) + 4 * 3翻譯成后綴表達式就是2 3 2 + + 4 3 * +，一旦你把式子翻譯成這樣的形式，接下來的處理就很容易了，我們可以用一個堆棧來保存操作數，遇到操作符，就從堆棧中彈出兩個操作數進行運算操作，2 3 2 + + 4 3 * +的處理過程為：
=>[2]
2入棧
=>[3 2] 3入棧
=>[2 3 2] 2入棧
=>+［ (2 3) 2] 讀到操作符+，彈出最上面兩個數2和3相加，得到5
=>[5 2] 結果入棧
=>+ [(5 2)] 讀到操作符+，彈出最上面兩個數5和2相加，得到7
=>[7] 結果入棧
=>[4 7] 4入棧
=>[3 4 7] 3入棧
=>* [(3 4) 7] 讀到操作符*，彈出最上面兩個數3和4相乘，得到12
=>[12 7] 結果入棧
=>+ [(12 7)] 讀到操作符＋，彈出最上面兩個數12和7相乘，得到19
=>[19] 結果入棧
結果保存在棧頂，這樣就完成了整個表達式的計算過程
最后，按照慣例，我貼出用LuckyScript編寫的表達式計算的完整代碼和運行結果，還是有少許問題的，比如表達式字符間不能包含空格，沒有處理浮點數，不過也懶得再改了
1
/**//*********************************************************************************
2
3LuckyScript測試程序：表達式計算器
4作者：清風
5
6
**********************************************************************************/
7
8#define TOKEN_TYPE_INT 0
9#define TOKEN_TYPE_FLOAT 1
10#define TOKEN_TYPE_OPEN_ROUND_BRACKET 2
11#define TOKEN_TYPE_CLOSE_ROUND_BRACKET 3
12#define TOKEN_OP_TYPE_ADD 4
13#define TOKEN_OP_TYPE_SUB 5
14#define TOKEN_OP_TYPE_MUL 6
15#define TOKEN_OP_TYPE_DIV 7
16#define TOKEN_OP_TYPE_MOD 8
17#define TOKEN_TYPE_END 9
18#define TOKEN_TYPE_INVALID 10
19
20#define MAX_STACK_SIZE 100
21#define true 1
22#define false 0
23
24//================================================================================
25// Experssion
26//================================================================================
27class Experssion
28
{
29public:
30 var mExprStr;
31 var mCurrLexeme;
32 var mStartIndex;
33};
34
35//================================================================================
36//Stack
37//================================================================================
38class Stack
39{
40public:
41 func init()
42
{
43 //清空堆棧
44 mTop = 0;
45
}
46
47 func push(var val)
48 {
49 if(mTop >= MAX_STACK_SIZE)
50 {
51 print("堆棧溢出!");
52 _getch();
53 }
54
55 mData[mTop] = val;
56 mTop ++;
57 }
58
59 func pop()
60 {
61 if(mTop < 0)
62 {
63 print("堆棧已沒有元素!");
64 _getch();
65 }
66
67 mTop --;
68 return mData[mTop];
69 }
70
71 func getTop()
72 {
73 return mTop;
74 }
75
76 func printAll()
77 {
78 for(var i = 0;i < mTop;i ++)
79 {
80 print(mData[i]);
81 }
82 }
83
84 func get(var index)
85 {
86 return mData[index];
87 }
88private:
89 var mTop;
90 var mData[MAX_STACK_SIZE];
91};
92
93//================================================================================
94//TokenGetter
95//================================================================================
96class TokenGetter
97{
98public:
99 //判斷字符是否數字
100 func isCharNumerber(var cChar)
101 {
102 if((cChar >= "0") && (cChar <= "9"))
103 {
104 return true;
105 }
106 else
107 {
108 return false;
109 }
110 }
111
112 //判斷字符是否分隔符
113 func isSeparator(var cChar)
114 {
115 return (cChar == "*") || (cChar == "/") || \
116 (cChar == "+") || (cChar == "-") || (cChar == "%") || \
117 (cChar == "(") || (cChar == ")");
118 }
119
120 //判斷字符串是否數字
121 func isStringNumber(var strString )
122 {
123 if(strlen(strString) == 0)
124 {
125 return false;
126 }
127
128 var strSize = strlen(strString);
129 for(var iCurrCharIndex = 0; iCurrCharIndex < strSize; iCurrCharIndex ++)
130 {
131 if((! isCharNumerber(strString[iCurrCharIndex])) && (! (strString[iCurrCharIndex] == "-")))
132 {
133 return false;
134 }
135 }
136
137 for(iCurrCharIndex = 1; iCurrCharIndex < strSize; iCurrCharIndex ++)
138 {
139 if(strString[iCurrCharIndex] == "-")
140 {
141 return false;
142 }
143 }
144 return true;
145 }
146
147 //參數expr中保存了狀態，返回在此狀態中的下一個token
148 func getNextToken(var expr)
149 {
150 var startIndex = expr.mStartIndex;
151 var exprStr = expr.mExprStr;
152
153 var size = strlen(exprStr);
154 expr.mCurrLexeme = "";
155
156 if(exprStr[startIndex] == "")
157 {
158 //已到達字符串的末尾
159 return TOKEN_TYPE_END;
160 }
161
162 for(var index = startIndex;index < size;index ++)
163 {
164 if(isSeparator(exprStr[index]))
165 {
166 if(index == startIndex)
167 {
168 //單個分割符
169 expr.mCurrLexeme = exprStr[index];
170 index ++;
171 }
172 break;
173 }
174
175 //如不是分割符，則加到expr.mCurrLexeme中
176 expr.mCurrLexeme = _contractStr(expr.mCurrLexeme,exprStr[index]);
177 }
178
179 expr.mStartIndex = index;
180 //返回token
181 switch(expr.mCurrLexeme)
182 {
183 case "+":
184 return TOKEN_OP_TYPE_ADD;
185 case "-":
186 return TOKEN_OP_TYPE_SUB;
187 case "*":
188 return TOKEN_OP_TYPE_MUL;
189 case "/":
190 return TOKEN_OP_TYPE_DIV;
191 case "%":
192 return TOKEN_OP_TYPE_MOD;
193 case "(":
194 return TOKEN_TYPE_OPEN_ROUND_BRACKET;
195 case ")":
196 return TOKEN_TYPE_CLOSE_ROUND_BRACKET;
197 default:
198 if(isStringNumber(expr.mCurrLexeme))
199 {
200 return TOKEN_TYPE_INT;
201 }
202 else
203 {
204 print("unknown type!");
205 return TOKEN_TYPE_INVALID;
206 }
207 break;
208 }
209
210 return TOKEN_TYPE_INVALID;
211 }
212};
213
214//================================================================================
215//ExprParser
216//================================================================================
217class ExprParser
218{
219public:
220 //分析因子
221 func parseFactor(var expr)
222 {
223 var token = mTokenGetter.getNextToken(expr);
224
225 //因子有兩種：數字、括號內表達式
226 switch(token)
227 {
228 case TOKEN_TYPE_INT:
229 mSuffixExpr.push(atoi(expr.mCurrLexeme));
230 break;
231 case TOKEN_TYPE_OPEN_ROUND_BRACKET:
232 //遞歸調用
233 parseExpr(expr);
234 token = mTokenGetter.getNextToken(expr);
235 if(token != TOKEN_TYPE_CLOSE_ROUND_BRACKET)
236 {
237 print("expect ')'");
238 _getch();
239 }
240 break;
241 default:
242 print("invalid operand!");
243 _getch();
244 break;
245 }
246 }
247
248 //分析項
249 func parseTemp(var expr)
250 {
251 var token;
252 var op;
253 var out = false;
254
255 //分析第一個因子
256 parseFactor(expr);
257 while(1)
258 {
259 token = mTokenGetter.getNextToken(expr);
260
261 switch(token)
262 {
263 case TOKEN_OP_TYPE_MUL:
264 op = "*";
265 break;
266 case TOKEN_OP_TYPE_DIV:
267 op = "/";
268 break;
269 default:
270 expr.mStartIndex -= strlen(expr.mCurrLexeme);
271 out = true;
272 break;
273 }
274
275 if(out)
276 {
277 break;
278 }
279
280 parseFactor(expr);
281
282 //為構造后綴表達式，運算符最后推入棧
283 mSuffixExpr.push(op);
284 }
285 }
286
287 //分析表達式
288 func parseExpr(var expr)
289 {
290 var token;
291 var op;
292 var out = false;
293
294 //分析第一項
295 parseTemp(expr);
296
297 while(1)
298 {
299 token = mTokenGetter.getNextToken(expr);
300 switch(token)
301 {
302 case TOKEN_OP_TYPE_ADD:
303 op = "+";
304 break;
305 case TOKEN_OP_TYPE_SUB:
306 op = "-";
307 break;
308 case TOKEN_OP_TYPE_MOD:
309 op = "%";
310 break;
311 case TOKEN_TYPE_END:
312 out = true;
313 break;
314 case TOKEN_TYPE_CLOSE_ROUND_BRACKET:
315 out = true;
316 expr.mStartIndex -= strlen(expr.mCurrLexeme);
317 break;
318 default:
319 out = true;
320 print("invalid operator!");
321 _getch();
322 break;
323 }
324
325 if(out)
326 {
327 break;
328 }
329
330 parseTemp(expr);
331
332 //運算符入棧
333 mSuffixExpr.push(op);
334 }
335 }
336
337 func parse(var expr)
338 {
339 //初始化堆棧
340 mSuffixExpr.init();
341
342 parseExpr(expr);
343
344 //返回保存了后綴表達式的堆棧
345 return mSuffixExpr;
346 }
347
348private:
349 var mTokenGetter = TokenGetter;
350 var mSuffixExpr = Stack;
351};
352
353//================================================================================
354//ExprCalculator
355//================================================================================
356class ExprCalculator
357{
358public:
359 //計算后綴表達式的值
360 func calculate(var suffixExpr)
361 {
362#define PUSH_VALUE(operator) \
363oprend1 = mStack.pop();\
364oprend2 = mStack.pop();\
365mStack.push(oprend1 operator oprend2);
366
367 var top = suffixExpr.getTop();
368 var element;
369 var oprend1;
370 var oprend2;
371
372 mStack.init();
373
374 //得到每一個element，判斷類型，如是操作符就從堆棧中彈出兩個操作數
375 //進行相關運算，如是操作數則推棧保存
376 for(var i = 0;i < top;i ++)
377 {
378 element = suffixExpr.get(i);
379
380 switch(element)
381 {
382 case "+":
383 PUSH_VALUE(+);
384 break;
385 case "-":
386 PUSH_VALUE(-);
387 break;
388 case "*":
389 PUSH_VALUE(*);
390 break;
391 case "/":
392 PUSH_VALUE(/);
393 break;
394 case "%":
395 PUSH_VALUE(%);
396 break;
397 default:
398 mStack.push(element);
399 break;
400 }
401 }
402
403 return mStack.get(0);
404 }
405
406private:
407 var mStack = Stack;
408};
409
410//================================================================================
411//Main
412//================================================================================
413func Main()
414{
415 var parser = new ExprParser();
416 var expr = new Experssion("","",0,0);
417 var calculator = new ExprCalculator();
418 var tokenGetter = new TokenGetter();
419 var suffixExpr;
420
421 print("**********************************************");
422 newLine();
423 print("LuckyScript測試程序: 表達式計算器");
424 newLine();
425 print("**********************************************");
426 newLine();
427 newLine();
428
429 while(1)
430 {
431 expr.mStartIndex = 0;
432 print("請輸入一個表達式，如要結束，輸入q: ");
433 expr.mExprStr = getInputString();
434
435 if(expr.mExprStr == "q")
436 {
437 break;
438 }
439
440 suffixExpr = parser.parse(expr);
441
442 print("后綴表達式：");
443 //輸出后綴表達式
444 suffixExpr.printAll();
445
446 newLine();
447
448 print("返回結果：");
449 //計算結果
450 print(calculator.calculate(suffixExpr));
451
452 newLine();
453 }
454}
455
運行結果：
posted on 2009-03-25 19:08
清風 閱讀(1542)
評論(3) 編輯 收藏 引用 所屬分類:
LuckyScript