为了全面检查脚本存在的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
清風 阅读(1511)
评论(3) 编辑 收藏 引用 所属分类:
LuckyScript