数据结构课程设计报告---算术表达式求值系统.doc

数据结构课程设计报告算术表达式求值系统学 号： 姓 名： 班 级： 指导教师： 成 绩： 完成时间： 2011.01.02 一、 设计题目描述和要求1. 问题:现在的计算器只能对简单的数进行运算,对复杂的多项表达式不能运算2. 解决方案：设计一个表达式求值系统3. 要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用下表给出的算符优先关系，实现对算术四则混合运算表达式的求值。 算术四则运算的规则： a. 从左算到右 b. 先乘除，后加减 c. 先括号内，后括号外根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系，它们优先关系如下表所示。二、 系统分析与概要设计根据问题描述和要求，系统要求能够正确求出算术表达式的值。在进行算术表达式求值过程中，考虑到我们输入的是中缀表达式，采用后缀表达式比较容易计算，因此先将中缀表达式转换成后缀表达式。程序应该具有：“将算术表达式转化为后缀表达式”、“利用后缀表达式求值”等基本模块。由于有优先级的问题，根据优先级不同的运算符运算的次序是不同的，因此更具其优先级的大小抽象的将其定义为不同的大小。三、 详细设计和编码1. 数据类型定义表达式求值中运算符对应优先级的定义structchar ch;int pri;lpri7=,0,(,1,*,5,/,5,+,3,-,3,),6,rpri7=,0,(,6,*,4,/,4,+,2,-,2,),1;/运算符优先级的定义运算符的存储structchar datamaxsize;int top;op;/用栈存储运算符2.各模块算法描述 （1）计算栈顶运算符对应的数字i+结束return lprii.prilprii.ch=opi7 ?int i=0；输入:op开始nyn y（2）判断优先级return 0;return -1;结束return 1;leftpri(op1)=0&*exp=0&*postexp=9？d=0c=b/a;st.top+;st.datast.top=c;a!=0?*postexp=/?a=st.datast.top; st.top-;b=st.datast.top;st.top-;c=ba;st.top+;st.datast.top=c; break;a=st.datast.top;st.top-;b=st.datast.top;st.top-;c=a*b;st.top+;st.datast.top=c;break;switch(*postexp)a=st.datast.top;st.top-;b=st.datast.top;st.top-;a=st.datast.top; st.top-;b=st.datast.top;st.top-;c=a+b;st.top+;st.datast.top=c; break;*postexp=0?*postexp=*?*postexp=-?*postexp=+?（4）后缀表达式求值ynynynynynynyn返回st.datast.top结束postexp+st.top+;st.datast.top=d; break;输出除零错误退出(5)主函数输入:表达式expchar exp20;char postexp;开始将中缀表达式exp转换为后缀表达式postexp输出：中缀表达式exp后缀表达式postexp表达式值compvalue(postexp)结束四、 调试分析写程序容易调程序难，调试要求：不仅要有很好的阅读程序的能力，更要有理解，分析和纠错能力。这次在调试过程中发现就是偶尔能运行成功，偶尔不能，只要不用加减就能成功，一旦用加减就运行不了。最后发现原来加与减弄反了。五、 测试结果 进入多项式求值系统请输入表达式:4+5*6-2中缀表达式:4+5*6-2后缀表达式:4#5#6#*+2#-表达式的值:32q键退出,其它键继续请选择:h 进入多项式求值系统请输入表达式:(56-20)/(6-2)-5中缀表达式:(56-20)/(6-2)-5后缀表达式:56#20#-6#2#-/5#-表达式的值:4q键退出,其它键继续请选择:qpress any key to continue六、 小结利用表达式求值的过程中思路是：输入的是中缀表达式，为了便于求值，先将中缀表达式转换成后缀表达式，再利用后缀表达式求值。在转换的过程中，考到了优先级，因此要对运算符号设定对应的值，就算是虚拟值吧。在编程的过程中，要细心，耐心，遇到问题不要急。七、 附录#include#include#include#define maxsize 30struct/设定运算符优先级char ch;int pri;lpri= =,0,(,1,*,5,/,5,+,3,-,3,),6,rpri= =,0,(,6,*,4,/,4,+,2,-,2,),1;int leftpri(char op)/求左运算符op的优先级for(int i=0;i7;i+)if(lprii.ch=op) return lprii.pri;int rightpri(char op)/求右运算符op的优先级for(int i=0;i7;i+)if(rprii.ch=op) return rprii.pri;int inop(char ch)/判断ch是否为运算符if(ch=(|ch=)|ch=+|ch=-|ch=*|ch=/)return 1;else return 0;int precede(char op1,char op2)/op1和op2运算符优先级的比较结果if(leftpri(op1)=rightpri(op2)return 0;else if(leftpri(op1)=0&*exp=0&*postexp=9)d=d*10 + *postexp - 0;postexp+;top+;stop=d;postexp+;/继续处理其他的字符returnstop;void main()char ch=a;char exp20;while(ch!=q&ch!=q)coutttt进入表达式求值系统endl;coutex