资源描述：
《算术表达式求值演示程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数理学院课程设计报告书课程名称数据结构课程设计设计题目算术表达式求值演示专业班级学号姓名指导教师2014年12月1设计时间2014年12月23~2014年12月29日2设计目的设计一个程序，演示算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。3设计任务(1)设置运算符栈和运算数栈辅助分析算符优先关系；(2)在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算；(3)在识别出运算数的同时，要将其字符序列形式转换成整数形式；(4)在程序的适当位置输出运算符栈、运算
2、数栈、输入字符和主要操作的内容。4设计内容4.1需求分析4.1.1该程序能实现算术四则运算表达式的求值，显示运算过程。4.1.2输入的形式：表达式，例如5*（3+7）#。包含的运算符只能有'+'、'-'、'*'、'/'、'('')'；4.1.3输出的形式：运算结果，50。4.1.4程序所能达到的功能：对表达式求值并输出。4.2总体设计4.2.1①.栈的抽象数据类型定义：ADTStack{数据对象：D={ai
3、ai∈Char,i=1,2.......,n,n≥0}数据关系：R1={＜ai-1,ai＞
4、ai-1,ai∈D,i
5、=2,3....n}约定an端为栈顶，ai端为栈底4.2.2基本操作：InitStack(&S)操作结果：构造一个空栈S。GetTop(S)初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push(&S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop(&S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1,c2)初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op
6、,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack主程序的流程：EvaluateExpression()函数实现了对表达式求值的功能，main()函数直接调用EvaluateExpression()对输入的表达式求值输出。算法流程图4.2.3函数的调用关系图ReturnOpOrdmainprecedeInPopPushEvaluateExpre
7、ssion输出Operate4.3详细设计4.3.1①.Precede(charc1,charc2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+><<<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=算法伪代码如下：charPrecede(charc1,charc2){staticchararray[49]={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','
8、>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','!','>','>','>','>','!','>','>','<','<','<','<','<','!','='};//用一维数组存储49种情况switch(c1){/*i为下面array的横标*/case'+':i=0;break;case'-':i=1;break;case'*':i=2;break;case'/':i=3;break;case'(':i=4;break;case
9、')':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'#':j=6;break;}return(array[7*i+j]);/*返回运算符array[7*i+j]为对应的c1,c2优先关系*/}②利用该算法对算术表达式4*(6-2)求
10、值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#4*(6-2)#Push(OPND,’4’)2#4*(6-2)#Push(OPTR,’*’)3#*4(6-2)#Push(OPNR,’(’)4#*(46-2)#Push(OPND,’6’)5#*(46-2)#Push(OPNR,’-’)6#*(-462)#P
