为了全面检查脚本存在的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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*********************************************************************************
2![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
3
LuckyScript测试程序:表达式计算器
4
作者:清风
5![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
6
**********************************************************************************/
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
#define MAX_STACK_SIZE 100
21
#define true 1
22
#define false 0
23![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
24
//================================================================================
25
// Experssion
26
//================================================================================
27
class Experssion
28![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
29
public:
30
var mExprStr;
31
var mCurrLexeme;
32
var mStartIndex;
33
};
34![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
35
//================================================================================
36
//Stack
37
//================================================================================
38
class Stack
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
40
public:
41
func init()
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
43
//清空堆栈
44
mTop = 0;
45
}
46
47
func push(var val)
48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
49
if(mTop >= MAX_STACK_SIZE)
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
51
print("堆栈溢出!");
52
_getch();
53
}
54
55
mData[mTop] = val;
56
mTop ++;
57
}
58
59
func pop()
60![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
61
if(mTop < 0)
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
print("堆栈已没有元素!");
64
_getch();
65
}
66
67
mTop --;
68
return mData[mTop];
69
}
70
71
func getTop()
72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
73
return mTop;
74
}
75
76
func printAll()
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
78
for(var i = 0;i < mTop;i ++)
79![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
80
print(mData[i]);
81
}
82
}
83
84
func get(var index)
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
86
return mData[index];
87
}
88
private:
89
var mTop;
90
var mData[MAX_STACK_SIZE];
91
};
92![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
93
//================================================================================
94
//TokenGetter
95
//================================================================================
96
class TokenGetter
97![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
98
public:
99
//判断字符是否数字
100
func isCharNumerber(var cChar)
101![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
102
if((cChar >= "0") && (cChar <= "9"))
103![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
104
return true;
105
}
106
else
107![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
108
return false;
109
}
110
}
111
112
//判断字符是否分隔符
113
func isSeparator(var cChar)
114![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
115
return (cChar == "*") || (cChar == "/") || \
116
(cChar == "+") || (cChar == "-") || (cChar == "%") || \
117
(cChar == "(") || (cChar == ")");
118
}
119![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
120
//判断字符串是否数字
121
func isStringNumber(var strString )
122![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
123
if(strlen(strString) == 0)
124![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
125
return false;
126
}
127
128
var strSize = strlen(strString);
129
for(var iCurrCharIndex = 0; iCurrCharIndex < strSize; iCurrCharIndex ++)
130![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
131
if((! isCharNumerber(strString[iCurrCharIndex])) && (! (strString[iCurrCharIndex] == "-")))
132![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
133
return false;
134
}
135
}
136![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
137
for(iCurrCharIndex = 1; iCurrCharIndex < strSize; iCurrCharIndex ++)
138![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
139
if(strString[iCurrCharIndex] == "-")
140![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
141
return false;
142
}
143
}
144
return true;
145
}
146
147
//参数expr中保存了状态,返回在此状态中的下一个token
148
func getNextToken(var expr)
149![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
158
//已到达字符串的末尾
159
return TOKEN_TYPE_END;
160
}
161
162
for(var index = startIndex;index < size;index ++)
163![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
164
if(isSeparator(exprStr[index]))
165![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
166
if(index == startIndex)
167![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
200
return TOKEN_TYPE_INT;
201
}
202
else
203![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
204
print("unknown type!");
205
return TOKEN_TYPE_INVALID;
206
}
207
break;
208
}
209
210
return TOKEN_TYPE_INVALID;
211
}
212
};
213![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
214
//================================================================================
215
//ExprParser
216
//================================================================================
217
class ExprParser
218![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
219
public:
220
//分析因子
221
func parseFactor(var expr)
222![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
223
var token = mTokenGetter.getNextToken(expr);
224
225
//因子有两种:数字、括号内表达式
226
switch(token)
227![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
251
var token;
252
var op;
253
var out = false;
254
255
//分析第一个因子
256
parseFactor(expr);
257
while(1)
258![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
259
token = mTokenGetter.getNextToken(expr);
260
261
switch(token)
262![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
277
break;
278
}
279
280
parseFactor(expr);
281
282
//为构造后缀表达式,运算符最后推入栈
283
mSuffixExpr.push(op);
284
}
285
}
286
287
//分析表达式
288
func parseExpr(var expr)
289![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
290
var token;
291
var op;
292
var out = false;
293
294
//分析第一项
295
parseTemp(expr);
296
297
while(1)
298![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
299
token = mTokenGetter.getNextToken(expr);
300
switch(token)
301![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
327
break;
328
}
329
330
parseTemp(expr);
331
332
//运算符入栈
333
mSuffixExpr.push(op);
334
}
335
}
336
337
func parse(var expr)
338![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
339
//初始化堆栈
340
mSuffixExpr.init();
341
342
parseExpr(expr);
343
344
//返回保存了后缀表达式的堆栈
345
return mSuffixExpr;
346
}
347
348
private:
349
var mTokenGetter = TokenGetter;
350
var mSuffixExpr = Stack;
351
};
352![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
353
//================================================================================
354
//ExprCalculator
355
//================================================================================
356
class ExprCalculator
357![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
358
public:
359
//计算后缀表达式的值
360
func calculate(var suffixExpr)
361![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
362
#define PUSH_VALUE(operator) \
363
oprend1 = mStack.pop();\
364
oprend2 = mStack.pop();\
365
mStack.push(oprend1 operator oprend2);
366![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
378
element = suffixExpr.get(i);
379
380
switch(element)
381![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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
406
private:
407
var mStack = Stack;
408
};
409![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
410
//================================================================================
411
//Main
412
//================================================================================
413
func Main()
414![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
431
expr.mStartIndex = 0;
432
print("请输入一个表达式,如要结束,输入q: ");
433
expr.mExprStr = getInputString();
434
435
if(expr.mExprStr == "q")
436![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
运行结果:
posted on 2009-03-25 19:08
清風 阅读(1508)
评论(3) 编辑 收藏 引用 所属分类:
LuckyScript