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

1、题目：设计一个程序实现基于二叉树表示的算术表达式的操作。一、 需求分析1、以二叉树为基本模型，构建了表达式二叉树。算术表达式的合法输入数据包括变量（,az）、常量（09）和二元运算符（，（乘幂），一元运算符（sin， cos，tan）。演示程序以人机对话的方式执行，即在计算机上显示提示信息后，由用户在键盘上输入对应的数据或命令，程序将执行相应的操作并显示下一步信息。表达式的输出主要是用带括号的中缀表示式输出调用函数InorderExp( ExpTree E, Status ( * Visit )( ExpTree e ) );2、 程序的目的实现算术表达式在计算机里的树形存储，实现基本的运算（

2、，（乘幂）sin，cos，tan），求偏导，常数合并。3、 测试数据（ 附后 ）。提供两种方式的测试：一种是自动测试，即程序调用test文件夹data.txt文件里的测试数据，另一种方式是手动测试，即按程序提示一步一步输入测试。除了满足要求的0; a; -91; +a*bc; +*5x2*8x; +*3x3*2x2x6，还有几十组数据测试。每当输入一个表达式后，程序提示用户赋值，再对表达式求值。为了方便用户，我在程序中用数组保存着一些测试数据，以供测试用。二、概要设计1以字符串保存输入的字符序列。2提示用户赋值的同时将数据取出建立二叉树。3用后根遍历的次序用递归函数对表达式求值，求值时进行相应

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;

4、/* 左右孩子指针 */ *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

5、( 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.构造一

6、个新的复合表达式(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

7、 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(

8、 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 );SEl

9、emType 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、存放表达式的结构类型，是以二叉树为基本原型。typed

10、ef enum OPER, VAR, ORD ElemTag;/运算符，变量，常量typedef struct ExpNodeElemTag tag;/标记unionchar expr4;/存放运算符名structchar var;/存放变量名int val;/存放变量的值，初始值为0vary;/存放变量int ordina; /存放常量值;struct ExpNode *lchild, *rchild;/* 左右孩子指针 */ *ExpTree;/* 二叉树的二叉链表存储表示 */我原来是直接用二叉树的存储结构的，后来发现受到这个结构类型的很大限制，受到广义表存储结构的启发，就自己设计了这样

11、一个存储类型。下面分析这个存储结构：（1）、用ElemTag tag;来标记是运算符，变量，常量。用枚举类型定义typedef enum OPER, VAR, ORD ElemTag，可以区分是运算符，变量，常量。（2）、用字符串char expr4;来存放运算符名，我先预定存放三个字符的运算符名（最后一个char用来存放0），这样运算符不仅可以是'+' ， '-' ， '*'，'/'，''，还可以是sin,cos,tan。如果觉得三个字符不够，可以扩展。（3）、structchar var;/存放变量名float

12、 val;/存放变量的值，初始为0vary;/存放变量。这样在变量赋值后，还可以保存着变量名。可以用作如公式一样，重复赋值使用。（4）、使用int ordina;来存放常量值。这样赋值时，就扩大了赋值范围，可以是一个整形的范围，大大扩大了本程序的使用范围。但需要在赋值时使用，在输入时，还是得用09，这也是本程序的缺陷，有待改进。基本操作：int Random( int nMin, int nMax );/返回nMin到nMax之间的随机数void FindVary( char * c, char * e );/找出表达式中的变量Status ArrayCreateExp( ExpTree &a

13、mp;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

14、, 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

15、 ) );/波兰式输出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( Q

16、ueue &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 );

17、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 = VA

18、R )/变量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 ArrayCreateEx

19、p( 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&

20、#39; |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

21、' && 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 <= '9' )/数字E->tag = OR

22、D;E->ordina = chi - '0'else if( chi >= 'a' && chi <= 'z' ) /变量E->tag = VAR;E->vary.var = chi;E->vary.val = 0;else if( chi = '+' | chi = '-' | chi = '*' | chi = '/' | chi = '' )/运算符E->tag = OPER;E->expr0 =

23、 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(

24、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

25、 ) /右孩子优先级低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 =

26、 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 );

27、 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(

28、 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-&g

29、t;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->r

30、child->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、构造的表达式如图算术表

31、达式前缀表示：*+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 <= 'Z' | ei >= 'a' && ei <= 'z' ) i += 2

32、;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 Find

33、Vary( char *c, char * e )for( int i = 0; i < j; +i )if( ci = str )return TRUE; /重复return FALSE;void FindVary( char *c, char * e )/找出表达式中的变量int i = -1, j = 0;while( e+i )if( ei >= 'A' && ei <= 'Z' | ei >= 'a' && ei <= 'z' )if( ! j | ! IsR

34、epeat( 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' &&am

35、p; 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数组中读取字符串。我原来

36、只是从键盘读入数据，后来考虑改为可从文件读入，构建字符串，用字符串建树。方法一：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&

37、quot;);elseprintf("构造表达式树失败！");方法二：可以在主函数调用时使用CreateExp( T, chi, j=0);这样也可以。从这个例子，让我明白：很多时候，我们处理同一个问题，是可以有多种方法的。五、.用户使用说明1、本程序的运行环境是DOS操作系统，执行文件为：Expression.exe。2、进入演示程序后首先选择要调用的功能函数。3、之后进入各个字功能函数。 如选择“3”，进入“3.实现对变量V的赋值(V=c).”会看到如下的提示 本程序提供手动用户自己输入测试和自动程序本身调用数据测试两种方式。 输入“1”按任意键退出子函数，返回主界面4

38、、输入“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