《表达式求值c+ 数据结构课设报告》由会员分享，可在线阅读，更多相关《表达式求值c+ 数据结构课设报告（23页珍藏版）》请在金锄头文库上搜索。
1、 数据结构课程设计 院 别计算机与通信工程学院专 业计算机科学与技术班级学号 姓 名 指导教师成 绩2013 年 7 月 18 日目录一、设计课题3二、需求分析3三、算法设计3四、调试分析9五、用户手册10六、测试结果10七、附录（源代码）13八、参考文献21 1、 设计课题： 表达式求值二、需求分析： 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。3、 算法设计：概要说明：为实现上述程序功能， 1. 首先置操作数栈为空栈，表达式起始符为运算符栈的栈底元素； 2. 依次扫描表达式
2、中每个字符，若是操作数则进OPND栈；若是运算符，则 和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。 3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n位和小数点的运算。模块间调用关系： 调用 主程序模块输出模块 详细说明（ADT描述） ： ADT SqStack数据对象：D= |ElemSet,i=1,2,，n, n0数据对象：R1=|,i=2,，n约定端为栈顶，端为栈底。基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，e) 初始条件：栈S已存在
3、。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S，e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。 In(c) 操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1, c2) 初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。 EvaluateExpression() 初始条件：输入表达式合法。 操作结果：返回表达式的最终结果。ADT Stack流程图及主要函数模块说明:1. 数据类型： typedef struct d
4、ouble *base;double *top;int stacksize;SqStack1;typedef struct char *base;char *top;int stacksize;SqStack2;2. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一维数组存储49种情况switch(c1) /* i为下面array的横
5、标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j为下面array的纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case
6、# : j=6;break; return (array7*i+j); /* 返回运算符array7*i+j为对应的c1,c2优先关系*/ 3. int EvaluateExpression()主要操作函数。算法概要流程图：利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#Push(OPND,3)2#3*(7-2)#Push(OPTR,*)3#*3(7-2)#Push(OPNR,()4#*(37-2)#Push(OPND,7)5#*(3 7-2)#Push(OPNR,-)6#*(-3 72)#Push(OPND,2)7#*(-3
7、7 2)#Operate(7,-,2)8#*(3 5)#Pop(OPTR)9#*3 5#Operate(3,*,5)10#15#Return(GetTop2(OPND)表2算法伪代码如下：Status EvaluateExpression()/算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，/OP为运算符集合SqStack1 OPND;SqStack2 OPTR;char c,x,theta,y,d;double a=0,b=0,k=0,z=0;InitStack1(OPND);InitStack2(OPTR); Push2(OPTR,#);cout请输入您要求解的
8、表达式并以“#”结尾：endl;y=GetTop2(OPTR);c=getchar(); /printf(字符是%cn,c);while (c!=#|GetTop2(OPTR)!=#)if(!In(c)double d1=0,d2=1,e=0; / cout=0&c=0&c=9) d2/=10; c-=0; e+=d2*c;c=getchar();/while/if/coutchuliwan=d1endl; Push1(OPND,e);/c=getchar();/printf(字符是%cn,c);else y=GetTop2(OPTR);/coutyendl; d=Precede(y,c);/
9、coutthis isy d;switch(d) case:/退栈并将运算结果入栈 / coutworldendl; Pop2(OPTR,theta); Pop1(OPND,b); /coutbendl; Pop1(OPND,a); Push1(OPND,Operate(a,theta,b); break; case!: cout请输入正确的表达式：endl; break; /switch/while GetTop1(OPND,k); cout表达式结果为： kendl; return OK;/EvaluateExpression4. Operate为进行二元运算ab的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。伪代码如下： Status Operate(double a,char theta,char b)switch(theta) case+:return(a+b);break; case-:return(a-b);break; case*:return(a*b);break; case/:retur
