算术表达式与二叉树

PAGE目录TOC\o"1-2"\h\z\u一、系统开发的背景 1二、程序分析与设计 1（一） 程序任务要求 1（二） 程序模块结构设计 1三、系统的设计与实现 2（一） 输入语法正确的前缀表达式并构造表达式E：ReadExpre(E) 2（二） 用带括弧的中缀表达式输出表达式E：WriteExpre(E) 4（三） 实现对变量V的赋值（V=c）：Assign(V,c) 4（四）、对算术表达式E求值：Value(E) 5（五）、构造一个新的复合表达式（E1）P（E2）：CompoundExpr（P，E1，E2） 5四、系统测试 6（一） 测试voidmain()函数 6（二）、测试其他调用函数（ReadExpre(E)、WriteExpre(E)、Assign(V,c)、Value(E)、CompoundExpr（P，E1，E2）等） 6五、总结 9六、附件（全部代码） 9PAGE23算术表达式与二叉树一、系统开发的背景一个表达式和一棵二叉树之间，存在着自然的对应关系，为了实现基于二叉树表示的算术表达式的操作，因此编写这个程序。二、程序分析与设计程序任务要求假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。实现以下操作：ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。WriteExpre(E)—用带括弧的中缀表达式输出表达式E。Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。Value(E)—对算术表达式E求值。CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）程序模块结构设计通过对程序任务功能的分析，算术表达式与二叉树程序功能如图（1）所示。算数表达式与二叉树程序算数表达式与二叉树程序输入

语法

正确

的前缀表达式并构造表达式用带括号的中缀表达式输出表达式构造一个新的算数表达式实现对变量V的赋值对算数表达式E求值图1算术表达式与二叉树程序功能图通过上图的功能分析，把整个系统划分为4个模块：以字符序列的形式输入语法正确的前缀表达式并构造表达式E，该模块主要实现：，借助函数ReadExpre(E)来实现；用带括弧的中缀表达式输出表达式E，该模块主要实现：，借助函数WriteExpre(E)来实现；实现对变量V的赋值（V=c），该模块主要实现：借助函数Assign(V,c)来实现；对算术表达式E求值，该模块主要实现：，借助函数Value(E)来实现；构造一个新的复合表达式（E1）P（E2），该模块主要实现：，借助函数CompoundExpr（P，E1，E2）来实现三、系统的设计与实现输入语法正确的前缀表达式并构造表达式E：ReadExpre(E)该模块的具体代码如下所示。 /*以正确的前缀表示式并构造表达式E*/ StatusReadExpr(BiTree*E,char*exprstring) {SqStackS;//定义顺序栈S inti,len;/*len为表达式的长度*/ BiTreep,q; (*E)=(BiTree)malloc(sizeof(BiTNode));/*申请二叉树的根结点的空间*/ (*E)->lchild=NULL; (*E)->rchild=NULL; len=strlen(exprstring);/*len赋值为表达式的长度*/ if(len==1)/*表达式长度为1时，二叉树只有根结点*/ judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ else {judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ InitStack(&S);/*初始化栈*/ q=(*E); Push(&S,q);/*入栈*/ Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/ for(i=1;i<len&&!StackEmpty(S);i++)// {p=(BiTree)malloc(sizeof(BiTNode)); judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树的结点中*/ p->lchild=NULL; p->rchild=NULL; if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^') {/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/ if(!q->lchild) {q->lchild=p;Push(&S,p);q=p;} else {q->rchild=p;Push(&S,p);q=p;}} else/*不是运算符，运算符出栈*/ {if(!q->lchild) {q->lchild=p;Pop(&S,&q);} else {q->rchild=p;Pop(&S,&q);} } } if(StackEmpty(S)&&i>=len) returnOK;/*栈空且i>=len，说明输入的表达式是正确的*/ else /*输入的表达式是错误的*/ {printf("\n\t输入的表达式有误！"); returnERROR; } } }用带括弧的中缀表达式输出表达式E：WriteExpre(E) /*用带括弧的中缀表达式输出表达式*/ voidWriteExpr(BiTreeE) {if(E)/*树不为空*/ { /*先递归左子树*/ if(E->lchild&&E->lchild->data.tag==CHAR)/*E的左孩子不为空，且左孩子为字符*/ {if(Pri_Compare(E->data.c,E->lchild->data.c))/*E->data.c比E->lchild->data.c优先*/ {printf("("); WriteExpr(E->lchild); printf(")");}/*带括弧输出左子树*/ else WriteExpr(E->lchild);/*否则，不带括弧输出左子树*/ } else WriteExpr(E->lchild);/*否则，输出左子树*/ /*访问输出根结点的值*/ if(E->data.tag==INT) {printf("%d",E->data.num);} else printf("%c",E->data.c); /*后递归右子树*/ if(E->rchild&&E->rchild->data.tag==CHAR)/*E的右孩子不为空，且右孩子为字符*/ {if(Pri_Compare(E->data.c,E->rchild->data.c))/*E->data.c比E->rchild->data.c优先*/ {printf("("); WriteExpr(E->rchild);printf(")");}/*带括弧输出右子树*/ elseWriteExpr(E->rchild);/*否则，不带括弧输出右子树*/ } elseWriteExpr(E->rchild);/*否则，输出右子树*/ } }实现对变量V的赋值（V=c）：Assign(V,c)/*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/ voidAssign(BiTree*E,charV,intc,int*flag) {if(*E) {if((*E)->data.tag==CHAR&&(*E)->data.c==V)/*如果找到要赋值的变量，赋值*/ {(*E)->data.tag=INT;(*E)->data.num=c;*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*递归左子树*/ Assign(&((*E)->rchild),V,c,flag);/*递归左子树*/ } } /*指数运算函数，底数为x，指数为exp*/ longpower(intx,intexp) { longresult; inti; for(i=1,result=1;i<=exp;i++) result*=x; returnresult;}（四）、对算术表达式E求值：Value(E)/*对算术表达式求值*/ longValue(BiTreeE) {if(E)/*树不为空*/ {if(!E->lchild&&!E->rchild&&E->data.tag==INT) return(E->data.num); /*结点的左孩子和右孩子为空，为叶子结点，返回结点的值*/ returnOperate(Value(E->lchild),E->data.c,Value(E->rchild));/*运算求值，后根遍历的次序对表达式求值，其中参数递归调用了Value()函数求左子树的值和右子树的值*/ } }（五）、构造一个新的复合表达式（E1）P（E2）：CompoundExpr（P，E1，E2）/*构造一个新的复合表达式*/ voidCompoundExpr(charP,BiTree*E1,BiTreeE2) { BiTreeE; E=(BiTree)malloc(sizeof(BiTNode));/*申请一个结点存放运算符P*/ E->data.tag=CHAR; E->data.c=P;/*申请到的结点值为P*/ E->lchild=(*E1);/*结点的左孩子为E1*/ E->rchild=E2;/*结点的右孩子为E2*/ (*E1)=E;/*(*E1)为根结点*/ printf("\n\t表达式E复合成功！其表达式变为：\n"); WriteExpr(E);/*输出复合好的表达式*/ }四、系统测试测试voidmain()函数测试该函数时可以运行程序，来测试主函数是否运行正常，如图2所示界面：图2程序主界面图（二）、测试其他调用函数（ReadExpre(E)、WriteExpre(E)、Assign(V,c)、Value(E)、CompoundExpr（P，E1，E2）等）测试时全面运行程序，根据测试数据进行测试，如运行无误，则证明程序中函数无误。如下图3-图9所示。图3图4图5图6图7图8图9五、总结系统完成了基于二叉树表示的算术表达式的操作功能。系统在运算方面有不足，不能进行三角函数等方面的计算。程序在运行中界面不够友好等问题。我的收获是在数据结构中可以将输入输出的语句改为C语言的输入输出语句，写程序就要多动手，在一些瓶颈上可以另辟蹊径，用其他方式编写出来后更改为自己需要的方式。在整体上就要有一个好的构思，在数据结构学习上要有全面的观念来编写程序。经过这两周的编译，我感觉对二叉树的掌握更牢固了，整体上我都是用的二叉树处理实现各个功能。我感觉对于一个题目中处理函数尽量让他可以多功能中使用，这样编程效率会高一些。六、附件（全部代码） #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<string.h> #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW0 typedefintStatus;/*二叉树结点类型*/ typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedefstructTElemType {ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/ union {intnum;/*tag=INT时，为整型*/ charc;/*tag=CHAR时，为字符型*/}; }TElemType; /*二叉树的二叉链表存储表示*/ typedefstructBiTNode {TElemTypedata; structBiTNode*lchild,*rchild;/*左右孩子指针*/ }BiTNode,*BiTree; typedefBiTreeSElemType;/*栈SqStack的元素*/ typedefcharSElemType1;/*栈SqStack1的元素*/ #defineSTACK_INIT_SIZE10/*存储空间初始分配量*/ #defineSTACKINCREMENT2/*存储空间分配增量*/ /*两个顺序栈*/ typedefstructSqStack {SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/ SElemType*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间，以元素为单位*/ }SqStack;/*顺序栈*/ typedefstructSqStack1 {SElemType1*base;/*在栈构造之前和销毁之后，base的值为NULL*/ SElemType1*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间，以元素为单位*/ }SqStack1;/*顺序栈*/ /*顺序栈的基本操作*/ StatusInitStack(SqStack*S) {/*构造一个空栈S*/ (*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK;} StatusStackEmpty(SqStackS) {/*若栈S为空栈，则返回TRUE，否则返回FALSE*/ if(S.top==S.base) returnTRUE; else returnFALSE;} StatusPush(SqStack*S,SElemTypee) {/*插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/ { (*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e; returnOK;} StatusPop(SqStack*S,SElemType*e) {/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/ if((*S).top==(*S).base) returnERROR; *e=*--(*S).top; returnOK;} StatusGetTop(SqStackS,SElemType*e) {/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/ if(S.top>S.base) {*e=*(S.top-1); returnOK;} else returnERROR;} /*顺序栈的基本操作*/ StatusInitStack1(SqStack1*S) {/*构造一个空栈S*/ (*S).base=(SElemType1*)malloc(STACK_INIT_SIZE*sizeof(SElemType1)); if(!(*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK;} StatusStackEmpty1(SqStack1S) {/*若栈S为空栈，则返回TRUE，否则返回FALSE*/ if(S.top==S.base)returnTRUE; elsereturnFALSE;} StatusPush1(SqStack1*S,SElemType1e) {/*插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/ { (*S).base=(SElemType1*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1)); if(!(*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e; returnOK;} StatusPop1(SqStack1*S,SElemType1*e) {/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/ if((*S).top==(*S).base) returnERROR; *e=*--(*S).top; returnOK;} StatusGetTop1(SqStack1S,SElemType1*e) {/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/ if(S.top>S.base) {*e=*(S.top-1); returnOK;} else returnERROR;}#include<math.h>#include<stdio.h>/*全局变量*/ intsave_number[51];/*在按原表达式输入形式中，输入的常量保存到数组save_number中，常量最多为50个，0单元不用*/ charExpr_String[50]; StatusInput_Expr(char*string,intflag) {if(flag==0) printf("\n\n\t请输入正确的前缀表示式："); else printf("\n\t请以表达式的原书写形式输入正确表示式："); flushall();/*清理缓冲区*/ gets(string);/*从键盘输入一串字符串作为表达式*/ if(strlen(string)==1)/*输入的表达式字符串长度为1*/ if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入的表达式只有一个运算符*/ {printf("\n\t表达式只有一个字符，为运算符，错误！");returnERROR;} elseif((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z')) /*输入的表达式只有一个数字或字符*/ {printf("\n\t表达式只有一个字符！");returnOK;} else{printf("\n\t输入的字符不是运算符也不是变量常量，错误！");returnERROR;} returnOK;} /*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/ voidjudge_value(BiTree*E,char*string,inti) {if(string[i]>='0'&&string[i]<='9')/*为常量*/ {(*E)->data.tag=INT;(*E)->data.num=string[i]-48;} elseif(string[i]>=1&&string[i]<=20)/*为常量，常量存于数组save_number中*/ {(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];} else/*为变量*/ {(*E)->data.tag=CHAR;(*E)->data.c=string[i];}} /*以正确的前缀表示式并构造表达式E*/ StatusReadExpr(BiTree*E,char*exprstring) {SqStackS;//定义顺序栈S inti,len;/*len为表达式的长度*/ BiTreep,q; (*E)=(BiTree)malloc(sizeof(BiTNode));/*申请二叉树的根结点的空间*/ (*E)->lchild=NULL; (*E)->rchild=NULL; len=strlen(exprstring);/*len赋值为表达式的长度*/ if(len==1)/*表达式长度为1时，二叉树只有根结点*/ judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ else {judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ InitStack(&S);/*初始化栈*/ q=(*E); Push(&S,q);/*入栈*/ Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/ for(i=1;i<len&&!StackEmpty(S);i++)// {p=(BiTree)malloc(sizeof(BiTNode)); judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树的结点中*/ p->lchild=NULL; p->rchild=NULL; if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^') {/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/ if(!q->lchild) {q->lchild=p;Push(&S,p);q=p;} else {q->rchild=p;Push(&S,p);q=p;}} else/*不是运算符，运算符出栈*/ {if(!q->lchild) {q->lchild=p;Pop(&S,&q);} else {q->rchild=p;Pop(&S,&q);} } } if(StackEmpty(S)&&i>=len) returnOK;/*栈空且i>=len，说明输入的表达式是正确的*/ else /*输入的表达式是错误的*/ {printf("\n\t输入的表达式有误！"); returnERROR; } } } /*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/ StatusPri_Compare(charc1,charc2) { if((c1=='^'||c1=='*'||c1=='-'||c1=='+'||c1=='/')&&(c2=='^'||c2=='*'||c2=='-'||c2=='+'||c2=='/')) {/*c1和c2为运算符*/ if(c1=='^')/*c1为指数运算符，则当c2不为'^'时，c1比c2优先*/ {if(c2!='^') returnOK; else returnERROR;} elseif(c1=='*'||c1=='/')/*c1为乘法或除法运算符，则当c2为'+'或'-'，c1比c2优先*/ {if(c2=='^'||c2=='*'||c2=='/') returnERROR; else returnOK;} else returnERROR;/*其余，c1不比c2优先*/} else returnERROR;/*c1和c2不是运算符*/} /*用带括弧的中缀表达式输出表达式*/ voidWriteExpr(BiTreeE) {if(E)/*树不为空*/ { /*先递归左子树*/ if(E->lchild&&E->lchild->data.tag==CHAR)/*E的左孩子不为空，且左孩子为字符*/ {if(Pri_Compare(E->data.c,E->lchild->data.c))/*E->data.c比E->lchild->data.c优先*/ {printf("("); WriteExpr(E->lchild); printf(")");}/*带括弧输出左子树*/ else WriteExpr(E->lchild);/*否则，不带括弧输出左子树*/ } else WriteExpr(E->lchild);/*否则，输出左子树*/ /*访问输出根结点的值*/ if(E->data.tag==INT) {printf("%d",E->data.num);} else printf("%c",E->data.c); /*后递归右子树*/ if(E->rchild&&E->rchild->data.tag==CHAR)/*E的右孩子不为空，且右孩子为字符*/ {if(Pri_Compare(E->data.c,E->rchild->data.c))/*E->data.c比E->rchild->data.c优先*/ {printf("("); WriteExpr(E->rchild);printf(")");}/*带括弧输出右子树*/ elseWriteExpr(E->rchild);/*否则，不带括弧输出右子树*/ } elseWriteExpr(E->rchild);/*否则，输出右子树*/ } } /*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/ voidAssign(BiTree*E,charV,intc,int*flag) {if(*E) {if((*E)->data.tag==CHAR&&(*E)->data.c==V)/*如果找到要赋值的变量，赋值*/ {(*E)->data.tag=INT;(*E)->data.num=c;*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*递归左子树*/ Assign(&((*E)->rchild),V,c,flag);/*递归左子树*/ } } /*指数运算函数，底数为x，指数为exp*/ longpower(intx,intexp) { longresult; inti; for(i=1,result=1;i<=exp;i++) result*=x; returnresult;} /*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/ longOperate(intopr1,charopr,intopr2) {longresult; switch(opr) {case'+':/*加法*/ result=opr1+opr2; returnresult;break; case'-':/*减法*/ result=opr1-opr2; returnresult;break; case'*':/*乘法*/ result=opr1*opr2; returnresult;break; case'/':/*除法，除法是在整型类型上的除法*/ result=opr1/opr2; returnresult;break; case'^':/*指数运算*/ result=power(opr1,opr2); returnresult;break; default:break; } } StatusCheck(BiTreeE) {if(E&&E->data.tag==CHAR)/*树不为空*/ { if(E->data.c!='*'&&E->data.c!='^'&&E->data.c!='-'&&E->data.c!='+'&&E->data.c!='/') {printf("\n\t表达式中仍存在变量没有赋值！不能求出表达式的值！");returnERROR;} /*存在变量，提示信息，后返回ERROR*/ if(Check(E->lchild))/*递归左子树*/ Check(E->rchild);/*递归右子树*/ } } /*对算术表达式求值*/ longValue(BiTreeE) {if(E)/*树不为空*/ {if(!E->lchild&&!E->rchild&&E->data.tag==INT) return(E->data.num); /*结点的左孩子和右孩子为空，为叶子结点，返回结点的值*/ returnOperate(Value(E->lchild),E->data.c,Value(E->rchild)); /*运算求值，后根遍历的次序对表达式求值，其中参数递归调用了Value()函数求左子树的值和右子树的值*/ } } /*构造一个新的复合表达式*/ voidCompoundExpr(charP,BiTree*E1,BiTreeE2) { BiTreeE; E=(BiTree)malloc(sizeof(BiTNode));/*申请一个结点存放运算符P*/ E->data.tag=CHAR; E->data.c=P;/*申请到的结点值为P*/ E->lchild=(*E1);/*结点的左孩子为E1*/ E->rchild=E2;/*结点的右孩子为E2*/ (*E1)=E;/*(*E1)为根结点*/ printf("\n\t表达式E复合成功！其表达式变为：\n"); WriteExpr(E);/*输出复合好的表达式*/ } StatusRead_Inorder_Expr(char*string,char*pre_expr) {inti,j,len,char_number=1;/*len表示字符串string的长度，char_number是记录数组save_number[]的个数*/ intnumber;/*保存大于9的常量*/ charc,c1; SqStack1S;/*栈定义*/ InitStack1(&S);/*初始栈*/ Push1(&S,'#');/*先将字符'#'入栈，用来表示作为栈的最底一个元素*/ len=strlen(string);/*len为字符串string的长度*/ c=string[len-1];/*从字符串的最后一个字符开始向前扫描*/ i=len-1; while(!StackEmpty1(S)&&i>=0)/*栈不为空且i大于等于0*/ {if(c=='(')/*字符为'('*/ { Pop1(&S,&c);/*出栈，赋值给c*/ while(c!=')')/*假如c不为')',出栈*/ { *pre_expr++=c; if(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#')Pop1(&S,&c); else{printf("\n\t输入的表达式有误!");returnERROR;} } } elseif(c==')')/*字符为')'，入栈*/ { Push1(&S,c);} elseif(c>='0'&&c<='9')/*字符为'0'-'9'之间，循环扫描string前一个字符，后确定常量的大小*/ { number=c-48;/*number为第一个常量字符的ASCII码-48*/ for(c1=string[i-1],j=1;(c1>='0'&&c1<='9')&&i>=0;j++,i--)/*循环扫描string前一个字符，求出常量后赋给number*/ { number=(c1-48)*power(10,j)+number;/*number为扫描到的常量*/ c1=string[i-2];} save_number[char_number]=number;/*将number存入到数组save_number中，下标为char_number*/ *pre_expr++=char_number++;} elseif((c>='a'&&c<='z')||(c>='A'&&c<='Z'))/*字符为'a'-'z'或'A'-'Z'之间的变量*/ {/*string下一个字符不能为常量或变量，否则，出错*/ if((string[i-1]>='0'&&string[i-1]<='9')||(string[i-1]>='A'&&string[i-1]<='Z')||(string[i-1]>='a'&&string[i-1]<='z')) {printf("\n\t输入的表达式有误！");returnERROR;} else *pre_expr++=c;} elseif(c=='*'||c=='/')/*字符为运算符'*'或'/'*/ { while(GetTop1(S,&c1)&&(c1=='^'))/*将c与栈顶的字符c1比较优先级*/ {Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈字符c*/ } elseif(c=='+'||c=='-')/*字符为运算符'+'或'-'*/ { while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'||c1=='/'))/*将c与栈顶的字符c1比较优先级*/ {Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈运算符c*/ } elseif(c=='^')/*字符为运算符'^'*/ { Push1(&S,c);/*入栈运算符'^'*/ } else {printf("\n\t输入的表达式有误！"); returnERROR;}/*其他字符，错误，返回ERROR*/ i--;/*下一个字符*/ if(i>=0) c=string[i];/*i不小于0，c=string[i]循环下一个字符*/ else/*否则，将清空栈*/ while(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') {Pop1(&S,&c);*pre_expr++=c;} } Pop1(&S,&c);/*将'#'出栈*/ *pre_expr='\0';/*字符串结束符*/ if(i<0&&StackEmpty1(S))returnOK; elsereturnERROR;} /*将字符串exprstring反转过来*/ voidreversal_string(char*exprstring) { intlen,i,j; chartemp; len=strlen(exprstring);/*len为exprstring的长度*/ for(i=0,j=len-1;i<j;i++,j--)/*字符串前后两个字符对换*/ { temp=exprstring[i]; exprstring[i]=exprstring[j]; exprstring[j]=temp;} } /*常数合并操作函数，合并表达式E中所有常数运算*/ voidMergeConst(BiTree*E) { longresult; if((*E)->lchild&&(*E)->rchild)/*左右孩子不为空*/ { if((*E)->lchild->data.tag==INT&&(*E)->rchild->data.tag==INT)/*假如左右孩子为常量，合并*/ { result=Operate((*E)->lchild->data.num,(*E)->data.c,(*E)->rchild->data.num);/*常数合并运算，调用Operate()函数求值*/ (*E)->data.tag=INT;(*E)->data.num=result;/*修改之前的运算符为常量*/ free((*E)->lchild);/*释放左孩子*/ free((*E)->rchild);/*释放右孩子*/ (*E)->lchild=(*E)->rchild=NULL;/*左右孩子置空*/ } else { MergeConst(&((*E)->lchild));/*递归左孩子*/ MergeConst(&((*E)->rchild));/*递归右孩子*/ } } }//判断是否操作符intisoperator(charc){switch(c){case'+':returnTRUE;case'-':returnTRUE;case'*':returnTRUE;case'/':returnTRUE;case'^':returnTRUE;default:returnFALSE;}} /*主菜单*/ charmenu() { charchoice; printf("\n\t*************算术表达式与二叉树*************"); printf("\n\t********************************************"); printf("\n\t*1>>>输入正确的前缀表达式*"); printf("\n\t*2>>>带括弧的中缀表示式输出*"); printf("\n\t*3>>>对变量进行赋值*"); printf("\n\t*4>>>对算数表达式求值*"); printf("\n\t*5>>>构造一个新的复合表达式*"); printf("\n\t*0>>>退出*"); printf("\n\t********************************************"); printf("\n\t请输入你的选择(数字)>>>>>"); choice=getche(); returnchoice;} /*主函数*/ voidmain() { BiTreeE,E1;/*两个表达式E和E1*/ intflag=0;/*表达式E构造标志，为0表示未构造，为1表示已构造*/ longresult;/*保存算数表达式运算结果*/ charV,P;//V被赋值，P为符合表达式运算符 intc;//C要赋值 charstring[30];//字符串 while(1) { system("cls");//清屏 switch(menu()) { case'1':/*1>>>输入正确的前缀表达式*/ if(Input_Expr(Expr_String,0))//在flag=0时，初始输入 if(