算术表达式与二叉树

1、目录一、系统开发的背景 .1.二、系统分析与设计 .1.（一） 系统功能要求 .1.（二） 系统模块结构设计 .1.三、系统的设计与实现 .3.（一） 二叉树的遍历 .3.（二） 算术表达式求值 .5.四、系统测试 .9.（一） 测试二叉树遍历函数 .9.（二） 测试算术表达式求值函数.1.0五、总结.1.0.六、附件（代码、部分图表）.1.0（一） 程序代码.1.0.（ 二） 实验截图.1.5.1算术表达式与二叉树一、系统开发的背景为了方便进行基本的算术运算，减轻对数字较大的数操作时所带来的 麻烦，及其在运算过程中错误的避免。因此设计算术表达式与二叉树的程 序来解决此问题。二、系统分析与设计

2、（一）系统功能要求由于一个表达式和一棵二叉树之间，存在着自然的对应关系。遍写一个程序，实现基于二叉树表示的算术表达式的操作。算术表达式 内可以含有变量（az）、常量（09）和二元运算符（+, -, * , /,A（乘幕） 。具体实现以下操作：1 以字符序列的形式输入语法正确的前缀表达式并构造表达式。2 用带括弧的中缀表达式输出表达式。3 实现对变量 V 的赋值（V=c）,变量的初值为 0。4 对算术表达式 E 求值。（二） 系统模块结构设计通过对系统功能的分析，基于二叉树表示的算术表达式的功能 如图（ 1）所示。2图 1 基于二叉树表示的算术表达式的功能图通过上图的功能分析，把整个系统划分为主

3、要的两大个模块：1、 将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列，必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数BiTreeCreate(BiTree T)创建二叉树，void Preorder(BiTree T)先序遍历，voidInOrder(BiTree T)中序遍历，void PostOrder(BiTree T)后序遍历，intSumleaf(BiTree T) 统计叶结点的数目，int Depth(BiTree T)二叉树的深 度 6 个函数联合来实现；2、 计算中序遍历所得的算术表达式的值。其中先要将扫描得到的中缀 表达式转换为后缀表达式，然后利用栈的初

4、始化，进栈与取栈顶元素操作进行对后缀表达式进行计算。 该模块借助函数 void InitStack(SeqStack *S) 初始化栈，int PushStack(SeqStack *S,char e)进栈，int GetTop(SeqStack3S,char *e)取栈顶元素，void TranslateExpress(char str,char exp) 中缀表达式转后缀表达式，float ComputeExpress(char a)计算后缀表达式的值来实现；三、系统的设计与实现(一) 二叉树的遍历分析：首先构建一棵二叉树，然后依次输出每个遍历的序列。流程图如图 2 所示。二叉树的遍历图

5、2:二叉树的遍历流程图该模块的具体代码如下所示：#in clude#in clude#define MaxSize 50typedef struct float dataMaxSize;int top;OpStack;typedef structchar dataMaxSize;int top;SeqStack;typedef struct BiTNodeffiB诲図后序遍何计貝结点如4char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree Create(BiTree T)/ 用扩展先序遍历序列创建二叉树 char ch;

6、ch=getchar(); if(ch=0)T=NULL;else T=new BiTNode;T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild); return T; void Visit(char ch)/ 访问根节点Visit(T-data);int Sumleaf(BiTree T)/ int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)/sum+;m=Sumleaf(T-lchild);sum=sum+m;n=Sumleaf(T-rchild);sum=sum+n;re

7、turn sum; printf(%c ,ch);void Preorder(BiTree T)/ if(T=NULL) return;Visit(T-data);Preorder(T-lchild);Preorder(T-rchild);void InOrder(BiTree T)/ if(T=NULL)return;InOrder(T-lchild);Visit(T-data);InOrder(T-rchild);void PostOrder(BiTree T)/if(T=NULL)return;PostOrder(T-lchild);PostOrder(T-rchild);先序遍历中序遍

8、历后序遍历统计叶结点的数目该结点的左或右分支为空时5int Depth(BiTree T)/二叉树的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild); depr=Depth(T-rchild);dep=1+(depldepr?depl:depr);return dep;void main()BiTree T;int sum,k;printf( 请输入二叉树中的元素 ( 以扩展先序遍历序列输入 ):n);T=Create(T);printf( 先序遍历序列为 :);Preorder(T);printf(n);printf( 中

9、序遍历序列为 :);InOrder(T);printf(n);printf( 后序遍历序列为 :);PostOrder(T);printf(n); sum=Sumleaf(T); printf( 叶结点的数目为 :%dn,sum);k=Depth(T);printf( 二叉树的深度为 :%dn,k);6(二) 算术表达式求值分析：首先初始化一个栈，然后对相关的数据元素及运算符进栈，之后中缀表达式转后缀表达式计算出后缀表达式的值。 流程图如图 3 所示。图 3:算术表达式求值流程图该模块的具体代码如下所示：#in clude#in clude#in clude#in clude#in clude

10、#define NULL 0#define MaxSize 50typedef struct float dataMaxSize;int top;OpStack;typedef structchar dataMaxSize;int top;SeqStack;void In itStack(SeqStack *S)初始化栈 S-top=0; 7int StackEmpty(SeqStack S)/ 判断栈是否为空 if(S.top =0) return 1;else return 0; int PushStack(SeqStack *S,char e)进栈if(S-top=MaxSize) pr

11、intf(”栈已满，不能进栈 r);return 0; else S-dataS-top=e;S-top+;return 1; int PopStack(SeqStack *S,char *e)/ 删除栈顶元素 if(S-top=0) printf( 栈已空 n);return 0; else S-top-;*e=S-dataS-top;return 1; int GetTop(SeqStack S,char *e)/ 取栈顶元素 if(S.top=0&ch=0&ai=9)/ 如果是数字 value=0;while(ai!= ) /如果不是空格 value=10*value+a

12、i-0;i+; S.top+;S.dataS.top=value; / 处理后进栈 else / 如果是运算符 switch(ai) case+: x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-;result=x1+x2; S.top+; S.dataS.top=result; break; case-: x1=S.dataS.top; S.top-;x2=S.dataS.top; S.top-; result=x2-x1; S.top+; S.dataS.top=result; break; case*: x1=S.dataS.top;S.top

13、-; x2=S.dataS.top; S.top-; result=x1*x2; S.top+;S.dataS.top=result; break;case/:x 仁 S.dataS.top; S.top-;x2=S.dataS.top; S.top-;result=x2/x1; S.top+;S.dataS.top=result; break;caseA:x 仁 S.dataS.top; S.top-;x2=S.dataS.top; S.top-;result=float(pow(x1,x2); S.top+;S.dataS.top=result; break; i+;if( S.top !

14、=-1) /如果栈不空，将结果出栈并返回 result=S.dataS.top;S.top-; if(S.top=-1)return result;else printf(表达式错误);exit(-1); return 0; void mai n()char aMaxSize,bMaxSize;9float f;printf(请输入一个算术表达式：”)；scan f(%s, &a);printf(中缀表达式为：sn,a);Tran slateExpress(a,b); printf(后缀表达式为：%sn,b);f=ComputeExpress(b);printf(计算结果：%fn ,f

15、);四、系统测试（一）测试二叉树遍历函数：测试的结果如图 4图 4：二叉树的遍历concinue请输叉树中的元素C臥扩展先序遍历序列输入”& &3 32 2e e 2 23 32 2131310（二） 测试算术表达式求值函数：测试的结果如图 5, 6C:USER5AC:USER5A DMINISTRATQRDESiaOPDMINISTRATQRDESiaOP ff文件烹gbuggbug莒术表达式我值启灼.昇术表达貳：42-142-1为匸/3/3为：4 4 2 2 11 -3-3 / /tQcon七iinii吕.图 6五、总结系统完成了对基本的数学算术运算的求值的功能。系统不能对

16、更高一级的复合表达式（如三角函数等）求值，是其不足 之处。我的收获是经过不断的查询相关的书籍与有关的资料，使得我对原本 不熟的知识有了深刻的了解和认识。也让我能够更加独立的去学习，提高 了我的自主学习的能力。六、附件（代码、部分图表）（一）程序代码：#i nclude#i nclude字符串函数#in clude功能：分配字节的存储区，若内存不够返回0.#i nclude/ta ndard library标准库函数头文件，stdlib.h里面定义了五种类型、一些宏和通用工具函数#i nclude数学库函数#define NULL 0#define MaxSize 50Ass壬帛后计一工- -X

17、 X : :y y一达达果a an nCUS/口瀝8 85 5 2 2箱 T /讦算结果：2.000000PressPress負nyny keke coco contcont inue_inue_11typedef struct float dataMaxSize;12int top;OpStack;/ 存放数字的栈typedef structchar dataMaxSize;int top;SeqStack;/ 存放运算符的栈 typedef struct BiTNode char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiT

18、ree Create(BiTree T)/用扩展先序遍历序列创建二叉树 char ch;ch=getchar(); if(ch=0) T=NULL;else T=new BiTNode; T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild); return T;void Visit(char ch)/访问根节点sum+; m=Sumleaf(T-lchild);sum=sum+m; n=Sumleaf(T-rchild);sum=sum+n; printf(%c ,ch); voidPreorder(BiTree T)/ i

19、f(T=NULL) return;Visit(T-data);Preorder(T-lchild);Preorder(T-rchild);void InOrder(BiTree T)/ if(T=NULL) return;InOrder(T-lchild);Visit(T-data);InOrder(T-rchild); voidPostOrder(BiTree T)/ if(T=NULL) return;PostOrder(T-lchild);PostOrder(T-rchild);Visit(T-data); 先序遍历中序遍历后序遍历int Sumleaf(BiTree T)/统计叶结点的

20、数目int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)/该结点的左或右分支为空时13return sum;int Depth(BiTree T)/二叉树的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild);depr=Depth(T-rchild); dep=1+(depldepr?depl:depr); return dep;void InitStack(SeqStack *S)/初始化栈 S-top=0; int StackEmpty(SeqStack S)/判断栈是否为空 if

21、(S.top =0) return 1;else return 0; int PushStack(SeqStack *S,char e)/进栈if(S-top=MaxSize) printf( 栈已满，不能进栈 !);return 0; else S-dataS-top=e;S-top+;return 1; int PopStack(SeqStack *S,char *e)/删除栈顶元素 if(S-top=0) printf( 栈已空 n);return 0; elseS-top-; *e=S-dataS-top;return 1; int GetTop(SeqStack S,char *e)

22、/取栈顶元素 if(S.top=0&ch=0&ai=9)/如果是数字 value=0; while(ai!= ) /如果不是空格 value=10*value+ai-0; i+; /相当于一个循环 , 把数组 a 值赋给 value.S.top+;S.dataS.top=value; / 处理后进栈 else / 如果是运算符switch(ai)case+:x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-;result=x1+x2; S.top+;S.dataS.top=result; break;case-:x1=S.dataS.t

23、op;S.top-; x2=S.dataS.top; S.top-;result=x2-x1; S.top+;S.dataS.top=result; break; case*:x1=S.dataS.top;S.top-; x2=S.dataS.top; S.top-;result=x1*x2;S.top+; S.dataS.top=result; break;case/: x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-; result=x2/x1; S.top+;S.dataS.top=result; break;case:x1=S.dataS.t

24、op; S.top-; x2=S.dataS.top; S.top-; result=float(pow(x1,x2); S.top+;15S.dataS.top=result; break; i+; if( S.top !=-1) / 如果栈不空，将结果出栈并返回 result=S.dataS.top;S.top-;if(S.top=-1) return result; else printf(表达式错误 );exit(-1); return 0; void main() BiTree T;int sum,k;printf( 请输入二叉树中的元素 ( 以扩展先序遍历序列输入T=Create(T);printf( 先序遍历序列为 :); Preorder(T); pri