文档介绍：实习报告
题目:编写一个实现基于二叉树表示的算术表达式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,E1,E2)――构造一个新的复合表达式(E1)p(E2)。
概要设计
1、数据类型的声明:
在这个课程设计中,采用了链表二叉树的存储结构,以及两个顺序栈的辅助存储结构
/*头文件以及存储结构*/
#include<>
#include<>
#include<>
#include<>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef 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为空栈,则返回TRUE,否则返回FALSE */
Statu