题目设计一个程序实现基于二叉树表示的算术表达式的操作.doc

题目：设计一个程序实现基于二叉树表示的算术表达式的操作。
一、 需求分析
1、以二叉树为基本模型，构建了表达式二叉树。算术表达式的合法输入数据包括变量（,a~z）、常量（0－9）和二元运算符（＋，－，＊，／，^（乘幂）），一元运算符（sin， cos，tan）。演示程序以人机对话的方式执行，即在计算机上显示提示信息后，由用户在键盘上输入对应的数据或命令，程序将执行相应的操作并显示下一步信息。表达式的输出主要是用带括号的中缀表示式输出调用函数InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );
2、 程序的目的实现算术表达式在计算机里的树形存储，实现基本的运算（＋，－，＊，／，^（乘幂））sin，cos，tan），求偏导，常数合并。
3、 测试数据（ 附后 ）。
提供两种方式的测试：一种是自动测试，即程序调用test文件夹data.txt文件里的测试数据，另一种方式是手动测试，即按程序提示一步一步输入测试。
除了满足要求的0; a; -91; +a*bc; +*5^x2*8x; +++*3^x3*2^x2x6，还有几十组数据测试。
每当输入一个表达式后，程序提示用户赋值，再对表达式求值。为了方便用户，我在程序中用数组保存着一些测试数据，以供测试用。

二、概要设计
1．以字符串保存输入的字符序列。
2．提示用户赋值的同时将数据取出建立二叉树。
3．用后根遍历的次序用递归函数对表达式求值，求值时进行相应的转化，将运算数的字符形式转换成整数形式。
4．用中缀表达式输出表达式时，适当添加括号，以正确反映运算的优先次序。
5．抽象数据类型的定义：
1)、存放表达式的结构类型，是以二叉树为基本原型。
typedef enum{ OPER, VAR, ORD }ElemTag;//运算符，变量，常量
typedef struct ExpNode
{
ElemTag tag; //标记
union{
char expr[4]; //存放运算符名
struct{
char var; //存放变量名
int val; //存放变量的值，初始值为0
}vary; //存放变量
int ordina; //存放常量值
};
struct ExpNode *lchild, *rchild; /* 左右孩子指针 */
} *ExpTree; /* 二叉树的二叉链表存储表示 */
基本操作：
int Random( int nMin, int nMax );
//返回nMin到nMax之间的随机数
void FindVary( char * c, char * e );
//找出表达式中的变量
Status ArrayCreateExp( ExpTree &E, char *ch, int &i );
//从ch数组中读取字符串，构造表达式
void CreateExp( ExpTree &E, char *ch, int &i ) ;
//Status InputCreateExp( ExpTree &E );
//从键盘先序输入来构造表达式树T
Status Visit( ExpTree e );
//输出e的内容
void InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );
//输出中序表达式用带括号的中缀表示式输出
Status Assign( ExpTree E, char v, float c ) ;
//对表达式内的所有v，赋值c
float Value( ExpTree E );
//计算表达式的值
ExpTree Compound( char p, ExpTree e1, ExpTree e2 );
//5.构造一个新的复合表达式(E1)P(E2)
Status Diff( ExpTree &E, char V );
//求表达式E对变量V的导数
void MergeConst( ExpTree E );
//合并表达式种所有常数运算
Status PreOrderTraverse( ExpTree E, Status ( * Visit )( ExpTree e ) );
//波兰式输出
Status PostOrderTraverse( ExpTree E, Status ( * Visit )( ExpTree e ) );
//逆波兰式输出

2)、队列
typedef char QElemType;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QuePtr;

typedef struct
{
QuePtr front;
QuePtr rear;
}Queue;

基本操作：
Status InitQueue( Queue &Q );
//构造一个空队列
Status DestroyQueue( Queue &Q );
//销毁队列
Status QueueEmpty( Queue Q );
//判空
Status EnQueue( Queue &Q, QElemType e );
//插入元素e为Q的新的队尾元素
Status DeQueue( Queue &Q, QElemType &e );
//删除队头元素，用e返回其值，并返回OK,否则返回ERROR;

3)、栈
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

基本操作：
Status InitStack( SqStack &S );
Status StackEmpty( SqStack S );
Status Push( SqStack &S, SElemType e );
Status Pop( SqStack &S, SElemType &e );
SElemType Top( 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 }ElemTag;//运算符，变量，常量
typedef struct ExpNode
{
ElemTag tag; //标记
union{
char expr[4]; //存放运算符名
struct{
char var; //存放变量名
int val; //存放变量的值，初始值为0
}vary; //存放变量
int ordina; //存放常量值
};
struct ExpNode *lchild, *rchild; /* 左右孩子指针 */
} *ExpTree; /* 二叉树的二叉链表存储表示 */

我原来是直接用二叉树的存储结构的，后来发现受到这个结构类型的很大限制，受到广义表存储结构的启发，就自己设计了这样一个存储类型。下面分析这个存储结构：
（1）、用ElemTag tag;来标记是运算符，变量，常量。用枚举类型定义typedef enum{ OPER, VAR, ORD }ElemTag，可以区分是运算符，变量，常量。
（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 FindVary( char * c, char * e );
//找出表达式中的变量
Status ArrayCreateExp( ExpTree &E, char *ch, int &i );
//从ch数组中读取字符串，构造表达式
void CreateExp( ExpTree &E, char *ch, int &i ) ;
//Status InputCreateExp( ExpTree &E );
//从键盘先序输入来构造表达式树T
Status Visit( ExpTree e );
//输出e的内容
void InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );
//输出中序表达式用带括号的中缀表示式输出
Status Assign( ExpTree E, char v, float c ) ;
//对表达式内的所有v，赋值c
float Value( ExpTree E );
//计算表达式的值
ExpTree Compound( char p, ExpTree e1, ExpTree e2 );
//5.构造一个新的复合表达式(E1)P(E2)
Status Diff( ExpTree &E, char V );
//求表达式E对变量V的导数
void MergeConst( ExpTree E );
//合并表达式种所有常数运算
Status PreOrderTraverse( ExpTree E, Status ( * Visit )( ExpTree e ) );
//波兰式输出
Status PostOrderTraverse( ExpTree E, Status ( * Visit )( ExpTree e ) );
//逆波兰式输出

2、队列。
typedef char QElemType;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QuePtr;

typedef struct
{
QuePtr front;
QuePtr rear;
}Queue;

基本操作：
Status InitQueue( Queue &Q );
//构造一个空队列
Status DestroyQueue( Queue &Q );
//销毁队列
Status QueueEmpty( Queue Q );
//判空
Status EnQueue( Queue &Q, QElemType e );
//插入元素e为Q的新的队尾元素
Status DeQueue( Queue &Q, QElemType &e );
//删除队头元素，用e返回其值，并返回OK,否则返回ERROR;

3、栈
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

基本操作：
Status InitStack( SqStack &S );
Status StackEmpty( SqStack S );
Status Push( SqStack &S, SElemType e );
Status Pop( SqStack &S, SElemType &e );
SElemType Top( SqStack S );

4、主函数和其他主要函数
1）、访问函数（输出函数）
Status Visit( ExpTree e )
//输出e的内容
{
int m, n[5];
if( e->tag == OPER ) //运算符
printf("%s", e->expr );
else if( e->tag == VAR ) //变量
{
if( !e->vary.val ) //变量的值是0
printf("%c", e->vary.var );//输出变量名
else
printf("%0.4f", e->vary.val );//输出变量的值
}
else //常量
{
if( e->ordina >= 0 ) //正数
printf("%d", e->ordina );
else
printf("(%d)", e->ordina ); //负数，输出时加括号
}
return OK;
}

2）、构造表达式
Status ArrayCreateExp( ExpTree &E, char *ch, int &i )
//从ch数组中读取字符串，构造表达式
{
if( ch[i] )
{
if( ! ( E = ( ExpTree )malloc( sizeof( ExpNode ) ) ) )
return ERROR;
if( ch[i] == 's' && ch[i+1] == 'i' && ch[i+2] == 'n' ||//sin
ch[i] == 'S' && ch[i+1] == 'I' && ch[i+2] == 'N' ||
ch[i] == 'c' && ch[i+1] == 'o' && ch[i+2] == 's' ||//cos
ch[i] == 'C' && ch[i+1] == 'O' && ch[i+2] == 'S' ||
ch[i] == 't' && ch[i+1] == 'a' && ch[i+2] == 'n' ||//tan
ch[i] == 'T' && ch[i+1] == 'A' && ch[i+2] == 'N' )
{
E->tag = OPER;
E->expr[0] = ch[i]; E->expr[1] = ch[++i]; E->expr[2] = ch[++i];
E->expr[3] = '\0';
ArrayCreateExp( E->rchild, ch, ++i );//只建右子树
E->lchild = NULL; //左子树为空
return OK;
}
else if( ch[i] >= '0' && ch[i] <= '9' ) //数字
{
E->tag = ORD;
E->ordina = ch[i] - '0';
}
else if( ch[i] >= 'a' && ch[i] <= 'z' ) //变量
{
E->tag = VAR;
E->vary.var = ch[i];
E->vary.val = 0;
}
else if( ch[i] == '+' || ch[i] == '-' || ch[i] == '*' || ch[i] == '/' || ch[i] == '^' )//运算符
{
E->tag = OPER;
E->expr[0] = ch[i];
E->expr[1] = '\0';
}
if( ! E->tag ) // E 是运算符
{
ArrayCreateExp( E->lchild, ch, ++i );
ArrayCreateExp( E->rchild, ch, ++i );
}
else
{
E->lchild = NULL;
E->rchild = NULL;
}
}
return OK;
}

3）、带括号的中缀表示式输出
void InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) )
//输出中序表达式用带括号的中缀表示式输出
{
int bracket;
if( E )
{
if( E->lchild )
{
bracket = precede( E, E->lchild );//比较双亲与左孩子运算符优先级
if( bracket > 0 ) //左孩子优先级低
printf("(");
InorderExp( E->lchild, Visit );
if( bracket > 0 )
printf(")");
}
Visit( E );
if( E->rchild )
{
bracket = precede( E, E->rchild );//比较双亲与右孩子运算符优先级
if( bracket >= 0 ) //右孩子优先级低
printf("(");
InorderExp( E->rchild, Visit );
if( bracket >= 0 )
printf(")");
}
}
}

4）、计算表达式的值
float Value( ExpTree E )
//计算表达式的值
{
float lv,rv,value = 0;
if( E )
{
if( E->tag == VAR ) //是变量
return ( E->vary.val );
if( E->tag == ORD )
return ( E->ordina );
if( E->lchild ) lv = Value( E->lchild );
rv = Value( E->rchild );
switch( E->expr[0] )
{
case '+': value = lv + rv; break;
case '-': value = lv - rv; break;
case '*': value = lv * rv; break;
case '/': if( rv ) value = lv / rv;
else exit( 0 );
break;
case '^': value = power( lv, rv ); break;
case 'S': case 's': value = sin( rv ); break;//sin
case 'T': case 't': value = tan( rv ); break;//tan
case 'C': case 'c':
if( E->expr[2] == 'S' || E->expr[2] == 's' )//cos
{ value = cos( rv );
break;
}
}
}
return ( value );
}

5）、合并常数
void MergeConst( ExpTree E )
//合并表达式中所有常数运算
{

if( ! E->lchild && ! E->rchild ) return; //叶子
if( E->tag == OPER && E->lchild && E->rchild && E->lchild->tag == ORD && E->rchild->tag == ORD )
{
E->tag = ORD;
switch( E->expr[0] )
{
case '*':
E->ordina = E->lchild->ordina * E->rchild->ordina; break;
case '/':
E->ordina = E->lchild->ordina / E->rchild->ordina; break;
case '^':
E->ordina = power( E->lchild->ordina, E->rchild->ordina ); break;
case '+':
E->ordina = E->lchild->ordina + E->rchild->ordina; break;
case '-':
E->ordina = E->lchild->ordina - E->rchild->ordina; break;
}
free( E->lchild );
free( E->rchild );
E->lchild = NULL;
E->rchild = NULL;
}
else
{
if( E->lchild )
MergeConst( E->lchild );
if( E->rchild )
MergeConst( E->rchild );
}
}

5、构造的表达式如图
算术表达式前缀表示：*+ab-cd
中缀带括号表示：（a+b）*(c-d)

*
+
-
a
b
c
d

四、 调试分析
1、调试过程中遇到了许多问题，下面举几个例子。
（1）赋值出错处理
在调试赋值函数时发生了“赋值失败的情况”
修改前的函数：
void FindVary( char *c, char * e )
//找出表达式中的变量
{
int i = -1, j = 0;
while( e[++i] )
if( e[i] >= 'A' && e[i] <= 'Z' || e[i] >= 'a' && e[i] <= 'z' ) {
i += 2;
continue; }
else
c[j++] = e[i];
c[j] = 0;
}
调试出现下面的情况

出现了两次了对X的赋值，原因是我在编写void FindVary( char *c, char * e )函数时，没有考虑到X重复出现两次（两次以上），我就在FindVary函数里加了函数Status IsRepeat( char *c, int j, char str )，用于判断是否重复，这样就可以错误。
修改后的函数：
Status IsRepeat( char *c, int j, char str )
//字符str是否c数组里的前j个元素字符相同
//是的话返回TRUE，否则返回FALSE
//为了简化void FindVary( char *c, char * e )
{
for( int i = 0; i < j; ++i )
if( c[i] == str )
return TRUE; //重复
return FALSE;
}

void FindVary( char *c, char * e )
//找出表达式中的变量
{
int i = -1, j = 0;
while( e[++i] )
if( e[i] >= 'A' && e[i] <= 'Z' || e[i] >= 'a' && e[i] <= 'z' )
if( ! j || ! IsRepeat( c, j, e[i] ) ) //j == 0||不重复
if( e[i] == 's' && e[i+1] == 'i' && e[i+2] == 'n' ||//sin
e[i] == 'S' && e[i+1] == 'I' && e[i+2] == 'N' ||
e[i] == 'c' && e[i+1] == 'o' && e[i+2] == 's' ||//cos
e[i] == 'C' && e[i+1] == 'O' && e[i+2] == 'S' ||
e[i] == 't' && e[i+1] == 'a' && e[i+2] == 'n' ||//tan
e[i] == 'T' && e[i+1] == 'A' && e[i+2] == 'N' ) {
i += 2;
continue; }
else
c[j++] = e[i];
c[j] = 0;
}
运行结果：

以后想问题要用穷举法，尽量考虑问题的时候考虑周全一点。

（2）在从ch数组中读取字符串。
我原来只是从键盘读入数据，后来考虑改为可从文件读入，构建字符串，用字符串建树。
方法一：
void CreateExp( ExpTree &E, char *ch, int &i )
//调用Status ArrayCreateExp( BiTree &T, char *ch, int &i )
//从ch数组中读取字符串，构造表达式，并用中缀表示式输出
{
i = 0;
if( ArrayCreateExp( E, ch, i ) )
{
printf("中缀表示式输出：");
InorderExp( E, Visit ); //输出中序表达式
printf("\n");
}
else
printf("构造表达式树失败！");
}

方法二：
可以在主函数调用时使用CreateExp( T, ch[i], j=0);这样也可以。

从这个例子，让我明白：很多时候，我们处理同一个问题，是可以有多种方法的。

五、.用户使用说明
1、本程序的运行环境是DOS操作系统，执行文件为：Expression.exe。
2、进入演示程序后首先选择要调用的功能函数。

3、之后进入各个字功能函数。
如选择“3”，进入“3.实现对变量V的赋值(V=c).”会看到如下的提示

本程序提供手动用户自己输入测试和自动程序本身调用数据测试两种方式。
输入“1”

按任意键退出子函数，返回主界面

4、输入“0”，退出。
六、测试结果
运行程序，进入主界面

1、以数组形式输入前缀表示式函数构造表达式. 输入“1”
运行结果：

2、以字符序列输入前缀表示式函数构造表达式.主界面输入“2”
1）输入“+++*3^x3*2^x2x6”
结果：

2）输入： 0
结果：

3）输入： a
结果：

4）输入： -91
结果：

5）输入： +a*bc
结果：

6）输入： +*5^x2*8x
结果：

3、实现对变量V的赋值(V=c).
A、手动测试
1）输入+a*bc
结果：

2）、输入：sinx
结果：

3）、输入：+6++*3^x3*2^x2x
结果：

B、自动测试：
1)

2)

3)

4、对算术表达式E求值.
A、手动测试
1)输入：^x3
结果：

2）输入：+++*3^x3*2^x2x6
结果：

3）输入：cosx
结果：

B、自动测试
1）

2)

3)

5、构造一个新的复合表示式(E1)P(E2)
A、手动测试
1）输入E1： +ab E2： -cd 运算符： *
结果：

2）输入E1： +6++*3^x3*2^x2x E2： *5^x3 运算符： /
结果：

B、自动测试
1）

2）

3）

6、求偏导函数Diff(E,V).

7、对三角函数的测试.
A、手动测试
1）输入：sinb
结果：

2）输入：cos+ab
结果：

3）输入：TANc
结果：

B、自动测试

1）

2）

3）

8、常数合并
数据是随机从8组数据抽取5组进行测试的，数据如下，
*-+23a+b*34 sin+12
COS*a+56 tan/+ab-35
-*+a/62b*56 SIN+34
COS-45 TAN*89

注：自动测试数据。保存在test/data里，如下：
0
a
-91
+a*bc
+*5^x2*8x
+++*3^x3*2^x2x6
+asinb
*-+23a+b*34
^*+abc/-efg
*+ab/cd
+5sinb
+*5^x2*8x
+6++*3^x3*2^x2x
+6+x+*3^x3*2^x2
^x3
*5^x3
sinx
sinb
SINc
tan3
+asinb
sin+ab
sin*1a
cosb
TANc
cos3
+acosb
cos+ab
TAN*1a
+a*bc
+*5^x2*8x
+++*3^x3*2^x2x6
sinx
+*5^x2*8x
+++*3^x3*2^x2x6
+6++*3^x3*2^x2x
+6+x+*3^x3*2^x4
*5^x3
sinb
SINc
tan3
+asinb
sin+ab
sin*1a
cosb
TANc
cos3
+acosb
cos+ab
TaN*1a
*-+23a+b*34
sin+12
COS*a+56
tan/+ab-35
-*+a/62b*56
SIN+34
COS-45
TAN*89

七、 附录
1、源程序文件名清单：
1）代码 / app / main.cpp //主函数的定义
代码 / app / expr.cpp //表示式操作的定义函数
代码 / app / queue.cpp //队列操作的定义函数
代码 / app / stack.cpp //栈操作的定义函数
2) 代码 / header / expr .h //表示式存储结构定义和操作的声名
代码 / header / queue .h //队列存储结构定义和操作的声名
代码 / header / stack .h //栈存储结构定义和操作的声名
2、测试数据保存在test / data . txt
3、调试过程中的图片保存在“图片”文件夹里

八、感想和心得
这次数据结构的课程设计可以说获益非浅，首先最深的感受是：机器是比任何教师都严厉的检查者。我们学的知识终于可以做出点东西来了！我们都已经大二了，说实话一直感觉课本知识按照老师说都是基础，一定要好好掌握，我们也照做了，我们考了个80，90多分。可是我们还是感到一种心虚，其实个人觉得好的学习应该在不断的有成就当中进行，当用自己所学的知道完成了任务的时候，那是一种成就感，是对自己学习的肯定，就会给自己带来无限的信心和继续学习的热情，我觉得不断地去实践并取得一定成果，这样学习是最好的。这次课程设计给了我们一次真正展现自己能力的机会，我通过自己的不断努力，我也终于成功了！