為了全面檢查腳本存在的BUG,必須要寫一個(gè)相對復(fù)雜的程序測試腳本,應(yīng)VCZH朋友的建議,我寫了這個(gè)表達(dá)式計(jì)算器,400多行代碼...我想沒人會(huì)用我這個(gè)腳本寫更長的程序了,對吧？因此,調(diào)試通過的同時(shí)也就意味著測試工作的暫告一段落，接下來得改進(jìn)內(nèi)存管理的一些問題．
鑒于上篇文章被管理員移除的教訓(xùn)，我決定稍微介紹一下表達(dá)式計(jì)算的方法，當(dāng)然都是些比較簡單的東西，考慮這樣一個(gè)表達(dá)式：2 + (3 + 2) + 4 * 3，結(jié)果等于多少？你很和諧的大腦應(yīng)該能很快就算出一個(gè)數(shù)字:19,是的，對了，那么你是怎么計(jì)算出來的呢？你的大腦思考過程大概就是：一眼看到括號，計(jì)算3+2=5,再計(jì)算2+5=7,看到乘號，計(jì)算4*3=12,最后相加=19．就是說，你的大腦把這個(gè)表達(dá)式分成了三項(xiàng)，2,(3+2),4*3，分別計(jì)算出值再按順序相加得到結(jié)果，用電腦計(jì)算表達(dá)式的處理過程也類似，首先我們根據(jù)優(yōu)先級把表達(dá)式分為三個(gè)層次：表達(dá)式、項(xiàng)、因子，每個(gè)加減號左右的操作數(shù)為項(xiàng)，每個(gè)乘除號左右的操作數(shù)為因子，在上面那個(gè)表達(dá)式中，項(xiàng)為2，(3 + 2)，4 * 3，因子為2,(3+2),4,3,所以，我們的處理順序是：計(jì)算因子的值－計(jì)算項(xiàng)的值－計(jì)算表達(dá)式的值，這可以通過遞歸實(shí)現(xiàn)，想象我們有這么幾個(gè)函數(shù)：parseExpr,parseTemp,parseFactor,對上面那個(gè)式子，首先ParseFactor處理因子2，處理完后返回到ParseTemp再返回到parseExpr，得到正確的操作符+,接著處理第二個(gè)項(xiàng)(3 + 2)，因?yàn)槭莻€(gè)表達(dá)式，所以到因子級別時(shí)遞歸調(diào)用parseExpr．．．一直到達(dá)表達(dá)式的末尾，為了方便處理，在編譯時(shí)，通常會(huì)把這樣的表達(dá)式翻譯為后綴表達(dá)式，2 + (3 + 2) + 4 * 3翻譯成后綴表達(dá)式就是2 3 2 + + 4 3 * +，一旦你把式子翻譯成這樣的形式，接下來的處理就很容易了，我們可以用一個(gè)堆棧來保存操作數(shù)，遇到操作符，就從堆棧中彈出兩個(gè)操作數(shù)進(jìn)行運(yùn)算操作，2 3 2 + + 4 3 * +的處理過程為：
=>[2]
2入棧
=>[3 2] 3入棧
=>[2 3 2] 2入棧
=>+［ (2 3) 2] 讀到操作符+，彈出最上面兩個(gè)數(shù)2和3相加，得到5
=>[5 2] 結(jié)果入棧
=>+ [(5 2)] 讀到操作符+，彈出最上面兩個(gè)數(shù)5和2相加，得到7
=>[7] 結(jié)果入棧
=>[4 7] 4入棧
=>[3 4 7] 3入棧
=>* [(3 4) 7] 讀到操作符*，彈出最上面兩個(gè)數(shù)3和4相乘，得到12
=>[12 7] 結(jié)果入棧
=>+ [(12 7)] 讀到操作符＋，彈出最上面兩個(gè)數(shù)12和7相乘，得到19
=>[19] 結(jié)果入棧
結(jié)果保存在棧頂，這樣就完成了整個(gè)表達(dá)式的計(jì)算過程
最后，按照慣例，我貼出用LuckyScript編寫的表達(dá)式計(jì)算的完整代碼和運(yùn)行結(jié)果，還是有少許問題的，比如表達(dá)式字符間不能包含空格，沒有處理浮點(diǎn)數(shù)，不過也懶得再改了
1
/**//*********************************************************************************
2
3LuckyScript測試程序：表達(dá)式計(jì)算器
4作者：清風(fēng)
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 //判斷字符是否數(shù)字
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 //判斷字符串是否數(shù)字
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 //參數(shù)expr中保存了狀態(tài)，返回在此狀態(tài)中的下一個(gè)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 //已到達(dá)字符串的末尾
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 //單個(gè)分割符
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 //因子有兩種：數(shù)字、括號內(nèi)表達(dá)式
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 //遞歸調(diào)用
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 //分析項(xiàng)
249 func parseTemp(var expr)
250 {
251 var token;
252 var op;
253 var out = false;
254
255 //分析第一個(gè)因子
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 //為構(gòu)造后綴表達(dá)式，運(yùn)算符最后推入棧
283 mSuffixExpr.push(op);
284 }
285 }
286
287 //分析表達(dá)式
288 func parseExpr(var expr)
289 {
290 var token;
291 var op;
292 var out = false;
293
294 //分析第一項(xiàng)
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 //運(yùn)算符入棧
333 mSuffixExpr.push(op);
334 }
335 }
336
337 func parse(var expr)
338 {
339 //初始化堆棧
340 mSuffixExpr.init();
341
342 parseExpr(expr);
343
344 //返回保存了后綴表達(dá)式的堆棧
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 //計(jì)算后綴表達(dá)式的值
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 //得到每一個(gè)element，判斷類型，如是操作符就從堆棧中彈出兩個(gè)操作數(shù)
375 //進(jìn)行相關(guān)運(yùn)算，如是操作數(shù)則推棧保存
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測試程序: 表達(dá)式計(jì)算器");
424 newLine();
425 print("**********************************************");
426 newLine();
427 newLine();
428
429 while(1)
430 {
431 expr.mStartIndex = 0;
432 print("請輸入一個(gè)表達(dá)式，如要結(jié)束，輸入q: ");
433 expr.mExprStr = getInputString();
434
435 if(expr.mExprStr == "q")
436 {
437 break;
438 }
439
440 suffixExpr = parser.parse(expr);
441
442 print("后綴表達(dá)式：");
443 //輸出后綴表達(dá)式
444 suffixExpr.printAll();
445
446 newLine();
447
448 print("返回結(jié)果：");
449 //計(jì)算結(jié)果
450 print(calculator.calculate(suffixExpr));
451
452 newLine();
453 }
454}
455
運(yùn)行結(jié)果：
posted on 2009-03-25 19:08
清風(fēng) 閱讀(1529)
評論(3) 編輯 收藏 引用 所屬分類:
LuckyScript