文档介绍：实习报告题目: 编写一个实现基于二叉树表示的算术表达式 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求值。(poundExpr(p,E 1,E2)――构造一个新的复合表达式( E1)p(E2)。二、概要设计 1 、数据类型的声明: 在这个课程设计中,采用了链表二叉树的存储结构,以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/ #include<> #include<> #include<> #include<> #define TRUE 1#define FALSE 0#define OK1#define ERROR 0#define OVERFLOW 0typedef int Status; 2、表达式的抽象数据类型定义 ADT Expression {数据对象 D:D是具有数值的常量 C和没有数值的变量 V; 数据关系: R={<(V 或者 C)P(V 或者 C)>|V,C ∈D,<(V 或者 C)P(V 或者 C)> 表示由运算符 P结合起来的表达式 E} 基本操作: Status Input_Expr( & string,flag) 操作结果:以字符序列的形式输入语法正确的前缀表达式,保存到字符串string ;参数 flag 表示输出的提示信息是什么,输入成功返回 OK, 否则,返回 ERROR 。 void judge_value( & E,& string,i) 初始条件:树 E存在,表达式的前缀字符串 string 存在; 操作结果:判断字符 string[i] ,如果是'0'-'9' 常量之间,二叉树结点E存为整型;否则,存为字符型。 Status ReadExpr( & E,& exprstring) 初始条件:表达式的前缀形式字符串 exprstring 存在; 操作结果:以正确的前缀表示式 exprstring 并构造表达式 E ,构造成功,返回 OK,否则返回 ERROR 。 Status pare(c1,c2) 初始条件: c1和c2是字符; 操作结果:如果两个字符是运算符,比较两个运算符的优先级, c1比 c2优先,返回 OK,否则返回 ERROR 。 void WriteExpr( &E)初始条件:表达式 E存在; 操作条件:用带括弧的中缀表达式输入表达式 E。 void Assign( & E,V,c, & flag) 初始条件:表达式 E存在, flag 为标志是否有赋值过; 操作结果:实现对表达式 E中的所有变量 V的赋值(V=c) 。 long Operate(opr1,opr,opr2) 初始条件:操作数 opr1 和操作数 opr2 以及操作运算符 opr; 操作结果:运算符运算求值,参数 opr1,opr2 为常量, opr 为运算符, 根据不同的运算符,实现不同的运算,返回运算结果。 Status Check(E) 初始条件:表达式 E存在; 操作结果:检查表达式 E是否还存在没有赋值的变量,以便求算数表达式E的值。 long Value(E) 初始条件:表达式 E存在; 操作结果:对算术表达式求值,返回求到的结果。 poundExpr(P, & E1,E2) 初始条件:表达式 E1和E2存在; 操作条件:构造一个新的复合表达式(E1)P(E2) 。 Status Read_Inorder_Expr( & string, & pre_expr) 操作结果:以表达式的原书写形式输入,表达式的原书写形式字符串 string 变为字符串 pre_expr ,后调用 reversal_string() 函数反转得到前缀表达式 pre_expr 。得到正确的前缀表达式返回 OK,否则,返回 ERROR 。 void MergeConst( & E) 操作结果:常数合并操作,合并表达式 E中所有常数运算。} ADT Expression 3 、整体设计 1 、顺序栈的基本操作: 对于栈 SqStack: Status InitStack(SqStack *S) /* 构造一个空栈 S */ Status StackEmpty(SqStack S) /* 若栈 S 为