题目：设计一个程序实现基于二叉树表示的算术表达式的操作。
一、需求分析
1、以二叉树为基本模型，构建了表达式二叉树。算术表达式的合法输入数据包括变量
（,a~z）、常量（0－9）和二元运算符（＋，－，＊，／，^（乘幂）），一元运算符（sin，cos，tan）。演示程序以人机对话的方式执行，即在计算机上显示提示信息后，由用户在键盘上输入对应的数据或命令，程序将执行相应的操作并显示下一步信息。表达式的输出主要是用带括号的中缀表示式输出调用函数InorderExp(ExpT ree E,S tatus(* Visit)(ExpT ree e));
2、程序的目的实现算术表达式在计算机里的树形存储，实现基本的运算（＋，－，＊，
／，^（乘幂））sin，cos，tan），求偏导，常数合并。
3、测试数据（附后）。
提供两种方式的测试：一种是自动测试，即程序调用test文件夹文件里的测试数据，另一种方式是手动测试，即按程序提示一步一步输入测试。
除了满足要求的0;a;-91;+a*bc;+*5^x2*8x;+++*3^x3*2^x2x6，还有几十组数据测试。
每当输入一个表达式后，程序提示用户赋值，再对表达式求值。为了方便用户，我在程序中用数组保存着一些测试数据，以供测试用。
二、概要设计
1．以字符串保存输入的字符序列。
2．提示用户赋值的同时将数据取出建立二叉树。
3．用后根遍历的次序用递归函数对表达式求值，求值时进行相应的转化，将运算数的字符形式转换成整数形式。
4．用中缀表达式输出表达式时，适当添加括号，以正确反映运算的优先次序。
5．抽象数据类型的定义：
1)、存放表达式的结构类型，是以二叉树为基本原型。
typedef enum{OPER,VAR,ORD}ElemT ag;//运算符，变量，常量
typedef struct ExpNode
{
ElemT ag tag;//标记
union{
char expr[4];//存放运算符名
struct{
char var;//存放变量名
int val;//存放变量的值，初始值为0
}vary;//存放变量
int ordina;//存放常量值
};
struct ExpNode*lchild,*rchild;/*左右孩子指针*/
}*ExpT ree;/*二叉树的二叉链表存储表示*/
基本操作：
int Random(int nMin,int nMax);
//返回nMin到nMax之间的随机数
void FindV ary(char*c,char*e);
//出表达式中的变量
S tatus ArrayCreateExp(ExpT ree&E,char*ch,int&i);
//从ch数组中读取字符串，构造表达式
void CreateExp(ExpT ree&E,char*ch,int&i);
//S tatus InputCreateExp(ExpT ree&E);
//从键盘先序输入来构造表达式树T
S tatus Visit(ExpT ree e);
//输出e的内容
void InorderExp(ExpT ree E,S tatus(*Visit)(ExpT ree e));
//输出中序表达式用带括号的中缀表示式输出
S tatus Assign(ExpT ree E,char v,float c);
//对表达式内的所有v，赋值c
float V alue(ExpT ree E);
//计算表达式的值
ExpT ree Compound(char p,ExpT ree e1,ExpT ree e2);
//5.构造一个新的复合表达式(E1)P(E2)
S tatus Diff(ExpT ree&E,char V);
/
/求表达式E对变量V的导数
void MergeConst(ExpT ree E);
//合并表达式种所有常数运算
S tatus PreOrderT raverse(ExpT ree E,S tatus(*Visit)(ExpT ree e)); //波兰式输出
S tatus P ostOrderT raverse(ExpT ree E,S tatus(*Visit)(ExpT ree e)); //逆波兰式输出
2)、队列
typedef char QElemT ype;
typedef struct QNode
{
QElemT ype data;
struct QNode*next;
}QNode,*QuePtr;
typedef struct
{
QuePtr front;
QuePtr rear;
}Queue;
基本操作：
S tatus InitQueue(Queue&Q);
//构造一个空队列
S tatus DestroyQueue(Queue&Q);
//销毁队列
S tatus QueueEmpty(Queue Q);
//判空
S tatus EnQueue(Queue&Q,QElemT ype e);
//插入元素e为Q的新的队尾元素
S tatus DeQueue(Queue&Q,QElemT ype&e);
//删除队头元素，用e返回其值，并返回OK，否则返回ERROR;
3)、栈
typedef struct
{
SElemType*base;
SElemType*top;
int stacksize;
}SqStack;
基本操作：
S tatus InitStack(SqStack&S);
S tatus StackEmpty(SqStack S);
S tatus Push(SqStack&S,SElemType e);
S tatus P op(SqStack&S,SElemType&e);
SElemType T op(SqStack S);
6、主程序：
void main()
{
while(1)
{接受命令
处理命令；
Switch()
{
case:  1.以数组形式输入前缀表示式函数构造表达式.
case:  2.以字符序列输入前缀表示式函数构造表达式.
case:  3.实现对变量V的赋值(V=c).
case:  4.对算术表达式E求值.\n");
case:  5.构造一个新的复合表示式(E1)P(E2).
case:  6.求偏导函数Diff(E,V)
case:7.对三角函数的测试.
case:8.常数合并.
case:0.结束
}
}
三、详细设计
1、存放表达式的结构类型，是以二叉树为基本原型。
typedef enum{OPER,VAR,ORD}ElemT ag;//运算符，变量，常量
typedef struct ExpNode
{
ElemT ag tag;//标记
union{
char expr[4];//存放运算符名
struct{
char var;//存放变量名
int val;//存放变量的值，初始值为0
}vary;//存放变量
int ordina;//存放常量值
};
struct ExpNode*lchild,*rchild;/*左右孩子指针*/
}*ExpT ree;/*二叉树的二叉链表存储表示*/
我原来是直接用二叉树的存储结构的，后来发现受到这个结构类型的很大限制，受到广义表存储结构的
启发，就自己设计了这样一个存储类型。下面分析这个存储结构：（1）、用ElemT ag tag；来标记是运算符，变量，常量。用枚举类型定义typedef enum{OPER, VAR,ORD}ElemT ag，可以区分是运算符，变量，常量。
（2）、用字符串char expr[4]；来存放运算符名，我先预定存放三个字符的运算符名（最后一个char用来存放’\0’），这样运算符不仅可以是'+'，'-'，'*'，'/'，'^'，还可以是’sin’,’cos’,’tan’。如果觉得三个字符不够，可以扩展。
（3）、struct{char var;//存放变量名float val;//存放变量的值，初始为0}vary;//存放变量。这样在变量赋值后，还可以保存着变量名。可以用作如公式一样，重复赋值使用。
（4）、使用int ordina；来存放常量值。这样赋值时，就扩大了赋值范围，可以是一个整形的范围，大大扩大了本程序的使用范围。但需要在赋值时使用，在输入时，还是得用0－9，这也是本程序的缺陷，有待改进。
基本操作：
int Random(int nMin,int nMax);
//返回nMin到nMax之间的随机数
void FindV ary(char*c,char*e);
//出表达式中的变量
S tatus ArrayCreateExp(ExpT ree&E,char*ch,int&i);
//从ch数组中读取字符串，构造表达式
void CreateExp(ExpT ree&E,char*ch,int&i);
//S tatus InputCreateExp(ExpT ree&E);
//从键盘先序输入来构造表达式树T
S tatus Visit(ExpT ree e);
//输出e的内容
void InorderExp(ExpT ree E,S tatus(*Visit)(ExpT ree e));
//输出中序表达式用带括号的中缀表示式输出
S tatus Assign(ExpT ree E,char v,float c);
//对表达式内的所有v，赋值c
float V alue(ExpT ree E);
//计算表达式的值
ExpT ree Compound(char p,ExpT ree e1,ExpT ree e2);
//5.构造一个新的复合表达式(E1)P(E2)
S tatus Diff(ExpT ree&E,char V);
//求表达式E对变量V的导数
void MergeConst(ExpT ree E);
//合并表达式种所有常数运算
S tatus PreOrderT raverse(ExpT ree E,S tatus(*Visit)(ExpT ree e));
/
/波兰式输出
S tatus P ostOrderT raverse(ExpT ree E,S tatus(*Visit)(ExpT ree e));
//逆波兰式输出
2、队列。
typedef char QElemT ype;
typedef struct QNode
{
QElemT ype data;
struct QNode*next;
}QNode,*QuePtr;
typedef struct
二叉树公式
{
QuePtr front;
QuePtr rear;
}Queue;
基本操作：
S tatus InitQueue(Queue&Q);
//构造一个空队列
S tatus DestroyQueue(Queue&Q);
//销毁队列
S tatus QueueEmpty(Queue Q);
//判空
S tatus EnQueue(Queue&Q,QElemT ype e);
//插入元素e为Q的新的队尾元素
S tatus DeQueue(Queue&Q,QElemT ype&e);
//删除队头元素，用e返回其值，并返回OK，否则返回ERROR;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。