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

题目：设计一个程序实现基于二叉树表示的算术表达式的操作。一、 需求分析1、以二叉树为基本模型，构建了表达式二叉树。算术表达式的合法输入数据包括变量（,az）、常量（09）和二元运算符（，（乘幂），一元运算符（sin， cos，tan）。演示程序以人机对话的方式执行，即在计算机上显示提示信息后，由用户在键盘上输入对应的数据或命令，程序将执行相应的操作并显示下一步信息。表达式的输出主要是用带括号的中缀表示式输出调用函数InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );2、 程序的目的实现算术表达式在计算机里的树形存储，实现基本的运算（，（乘幂）sin，cos，tan），求偏导，常数合并。3、 测试数据（ 附后 ）。提供两种方式的测试：一种是自动测试，即程序调用test文件夹data.txt文件里的测试数据，另一种方式是手动测试，即按程序提示一步一步输入测试。除了满足要求的0; a; -91; +a*bc; +*5x2*8x; +*3x3*2x2x6，还有几十组数据测试。每当输入一个表达式后，程序提示用户赋值，再对表达式求值。为了方便用户，我在程序中用数组保存着一些测试数据，以供测试用。二、概要设计1以字符串保存输入的字符序列。2提示用户赋值的同时将数据取出建立二叉树。3用后根遍历的次序用递归函数对表达式求值，求值时进行相应的转化，将运算数的字符形式转换成整数形式。4用中缀表达式输出表达式时，适当添加括号，以正确反映运算的优先次序。5抽象数据类型的定义：1)、存放表达式的结构类型，是以二叉树为基本原型。typedef enum OPER, VAR, ORD ElemTag;/运算符，变量，常量typedef struct ExpNodeElemTag tag;/标记unionchar expr4;/存放运算符名structchar var;/存放变量名int val;/存放变量的值，初始值为0vary;/存放变量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 ); /从键盘先序输入来构造表达式树TStatus Visit( ExpTree e );/输出e的内容void InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );/输出中序表达式用带括号的中缀表示式输出Status Assign( ExpTree E, char v, float c ) ;/对表达式内的所有v，赋值cfloat 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 QNodeQElemType data;struct QNode *next;QNode, *QuePtr;typedef structQuePtr 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 structSElemType *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 ExpNodeElemTag tag;/标记unionchar expr4;/存放运算符名structchar var;/存放变量名int val;/存放变量的值，初始值为0vary;/存放变量int ordina; /存放常量值;struct ExpNode *lchild, *rchild;/* 左右孩子指针 */ *ExpTree;/* 二叉树的二叉链表存储表示 */我原来是直接用二叉树的存储结构的，后来发现受到这个结构类型的很大限制，受到广义表存储结构的启发，就自己设计了这样一个存储类型。下面分析这个存储结构：（1）、用ElemTag tag;来标记是运算符，变量，常量。用枚举类型定义typedef enum OPER, VAR, ORD ElemTag，可以区分是运算符，变量，常量。（2）、用字符串char expr4;来存放运算符名，我先预定存放三个字符的运算符名（最后一个char用来存放0），这样运算符不仅可以是+ ， - ， *，/，还可以是sin,cos,tan。如果觉得三个字符不够，可以扩展。（3）、structchar var;/存放变量名float val;/存放变量的值，初始为0vary;/存放变量。这样在变量赋值后，还可以保存着变量名。可以用作如公式一样，重复赋值使用。（4）、使用int ordina;来存放常量值。这样赋值时，就扩大了赋值范围，可以是一个整形的范围，大大扩大了本程序的使用范围。但需要在赋值时使用，在输入时，还是得用09，这也是本程序的缺陷，有待改进。基本操作：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 ); /从键盘先序输入来构造表达式树TStatus Visit( ExpTree e );/输出e的内容void InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );/输出中序表达式用带括号的中缀表示式输出Status Assign( ExpTree E, char v, float c ) ;/对表达式内的所有v，赋值cfloat 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 QNodeQElemType data;struct QNode *next;QNode, *QuePtr;typedef structQuePtr 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 structSElemType *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, n5;if( e-tag = OPER )/运算符printf(%s, e-expr );else if( e-tag = VAR )/变量if( !e-vary.val )/变量的值是0printf(%c, e-vary.var );/输出变量名elseprintf(%0.4f, e-vary.val );/输出变量的值else/常量if( e-ordina = 0 )/正数printf(%d, e-ordina );elseprintf(%d), e-ordina );/负数，输出时加括号return OK;2）、构造表达式Status ArrayCreateExp( ExpTree &E, char *ch, int &i )/从ch数组中读取字符串，构造表达式if( chi )if( ! ( E = ( ExpTree )malloc( sizeof( ExpNode ) ) ) )return ERROR; if( chi = s & chi+1 = i & chi+2 = n |/sinchi = S & chi+1 = I & chi+2 = N |chi = c & chi+1 = o & chi+2 = s |/coschi = C & chi+1 = O & chi+2 = S |chi = t & chi+1 = a & chi+2 = n |/tanchi = T & chi+1 = A & chi+2 = N )E-tag = OPER;E-expr0 = chi;E-expr1 = ch+i;E-expr2 = ch+i;E-expr3 = 0;ArrayCreateExp( E-rchild, ch, +i );/只建右子树E-lchild = NULL; /左子树为空return OK;else if( chi = 0 & chi tag = ORD;E-ordina = chi - 0;else if( chi = a & chi tag = VAR;E-vary.var = chi;E-vary.val = 0;else if( chi = + | chi = - | chi = * | chi = / | chi = )/运算符E-tag = OPER;E-expr0 = chi;E-expr1 = 0;if( ! E-tag )/ E 是运算符ArrayCreateExp( E-lchild, ch, +i ); ArrayCreateExp( E-rchild, ch, +i ); elseE-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-expr0 )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;/sincase T: case t: value = tan( rv ); break;/tancase C: case c:if( E-expr2 = S | E-expr2 = s )/cosvalue = 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-expr0 )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;elseif( E-lchild )MergeConst( E-lchild );if( E-rchild )MergeConst( E-rchild );5、构造的表达式如图算术表达式前缀表示：*+ab-cd中缀带括号表示：（a+b）*(c-d)*+-abcd四、 调试分析1、调试过程中遇到了许多问题，下面举几个例子。（1）赋值出错处理在调试赋值函数时发生了“赋值失败的情况”修改前的函数：void FindVary( char *c, char * e )/找出表达式中的变量int i = -1, j = 0;while( e+i )if( ei = A & ei = a & ei = z ) i += 2;continue;elsecj+ = ei;cj = 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 = A & ei = a & ei = z )if( ! j | ! IsRepeat( c, j, ei ) )/j = 0|不重复if( ei = s & ei+1 = i & ei+2 = n |/sinei = S & ei+1 = I & ei+2 = N |ei = c & ei+1 = o & ei+2 = s |/cosei = C & ei+1 = O & ei+2 = S |ei = t & ei+1 = a & ei+2 = n |/tanei = T & ei+1 = A & ei+2 = N )i += 2;continue;elsecj+ = ei;cj = 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);elseprintf(构造表达式树失败！);方法二：可以在主函数调用时使用CreateExp( T, chi, j=0);这样也可以。从这个例子，让我明白：很多时候，我们处理同一个问题，是可以有多种方法的。五、.用户使用说明1、本程序的运行环境是DOS操作系统，执行文件为：Expression.exe。2、进入演示程序后首先选择要调用的功能函数。3、之后进入各个字功能函数。 如选择“3”，进入“3.实现对变量V的赋值(V=c).”会看到如下的提示 本程序提供手动用户自己输入测试和自动程序本身调用数据测试两种方式。 输入“1”按任意键退出子函数，返回主界面4、输入“0”，退出。六、测试结果运行程序，进入主界面1、以数组形式输入前缀表示式函数构造表达式. 输入“1”运行结果：2、以字符序列输入前缀表示式函数构造表达式.主界面输入“2”1）输入“+*3x3*2x2x6”结果：2）输入：0 结果：3）输入： a 结果：4）输入： -91 结果：5）输入： +a*bc 结果：6）输入： +*5x2*8x 结果：3、实现对变量V的赋值(V=c).A、手动测试 1）输入+a*bc 结果： 2）、输入：sinx 结果： 3）、输入：+6+*3x3*2x2x 结果： B、自动测试：1)2)3)4、对算术表达式E求值. A、手动测试 1)输入：x3 结果：2）输入：+*3x3*2x2x6 结果：3）输入：cosx 结果： B、自动测试1）2)3)5、构造一个新的复合表示式(E1)P(E2)A、手动测试1）输入E1： +ab E2： -cd 运算符： * 结果：2）输入E1： +6+*3x3*2x2x E2： *5x3 运算符： / 结果： 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 +*5x2*8x +*3x3*2x2x6 +asinb *-+23a+b*34 *+abc/-efg *+ab/cd +5sinb +*5x2*8x +6+*3x3*2x2x +6+x+*3x3*2x2 x3 *5x3 sinx sinb SINc tan3 +asinb sin+ab sin*1a cosb TANc cos3 +acosb cos+ab TAN*1a +a*bc +*5x2*8x +*3x3*2x2x6 sinx +*5x2*8x +*3x3*2x2x6 +6+*3x3*2x2x +6+x+*3x3*2x4 *5x3 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多分。可是我们还是感到一种心虚，其实个人觉得好的学习应该在不断的有成就当中进行，当用自己所学的知道完成了任务的时候，那是一种成就感，是对自己学习的肯定，就会给自己带来无限的信心和继续学习的热情，我觉得不断地去实践并取得一定成果，这样学习是最好的。这次课程设计给了我们一次真正展现自己能力的机会，我通过自己的不断努力，我也终于成功了！