算术表达式与二叉树课程设计

山西大学课程设计任务书设计题目算术表达式与二叉树所属课程：数据结构系另 IJ 软件学院专业软件工程班级软工 1408 班 姓名霍志斌指导教师李雪梅设计任务下达日期 2015 年 12 月 15 日 设计时间 2016 年 1 月 4 日 至 2016 年 1 月 8 日 录：一、需求分析二、概要设计1、数据类型的声明：2、表达式的抽象数据类型定义3、整体设计三、详细设计1、二叉树的存储类型2、顺序栈的存储类型3、表达式的基本操作4、主程序和其他伪码算法5、函数的调用关系四、设计和调试分析五、测试六、课程设计的心得和心得以及问题一、需求分析【课程设计要求】【问题的描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式 Expression 的操作。【基本要求】假设算术表达式 Expression 内可以含有变量(a-z)，常量(0-9)和二元运算符(+,-,*,/,八(乘幂))。实现以下操作：(1) ReadExpr(E)以字符序列的形式输入语法正确的前缀表达式并构造表达式 E。(2) WriteExpr(E)用带括号的中缀表达式输出表达式 E。(3) Assign(V,c)——实现对变量 V 的赋值(V 二 c),变量的初值为 0。(4) Value(E)——对算术表达式 E 求值。(5)-------------------------CompoundExpr(p,El,E2)构造一个新的复合表达式(El)p(E2)。【测试数据】1) 分别输入 0；a;-91;+a*bc;+*5x2*8x;+++*3"*2"x2x6 并输出。2)每当输入一个表达式后,对其中的变量赋值,然后对表达式求值。二、概要设计1、数据类型的声明：在这个课程设计中,采用了链表二叉树的存储结构,以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0typedefintStatus;2、表达式的抽象数据类型定义ADTExpression{数据对象 D：D 是具有数值的常量 C 和没有数值的变量 V；数据关系：R={〈(V 或者C)P(V 或者 C)〉|V,CWD,<(V 或者 C)P(V 或者 C)>表示由运算符 P 结合起来的表达式E}基本操作：StatusInput_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string；参数 flag 表示输出的提示信息是什么，输入成功返回 0K，否则，返回ERROR。voidjudge_value(&E,&string,i)初始条件：树 E 存在，表达式的前缀字符串 string 存在；操作结果：判断字符string[...