算术表达式与二叉树

1、 目录目录一、系统开发的背景一、系统开发的背景.1二、系统分析与设计二、系统分析与设计.1（一）（一） 系统功能要求系统功能要求.1（二）（二） 系统模块结构设计系统模块结构设计.1三、系统的设计与实现三、系统的设计与实现.3（一）（一） 二叉树的遍历二叉树的遍历.3（二）（二） 算术表达式求值算术表达式求值.5四、系统测试四、系统测试.9（一）（一） 测试二叉树遍历函数测试二叉树遍历函数.9（二）（二） 测试算术表达式求值函数测试算术表达式求值函数.10五、总结五、总结.10六、附件（代码、部分图表）六、附件（代码、部分图表）.10(一一) 程序代码程序代码.10( (二二) ) 实验截图实

2、验截图.151算术表达式与二叉树算术表达式与二叉树一、一、系统开发的系统开发的背景背景为了方便进行基本的算术运算，减轻对数字较大的数操作时所带来的麻烦，及其在运算过程中错误的避免。因此设计算术表达式与二叉树的程序来解决此问题。二、系统分析与设计二、系统分析与设计（一）（一）系统功能要求系统功能要求 由于一个表达式和一棵二叉树之间，存在着自然的对应关系。遍写一个程序，实现基于二叉树表示的算术表达式的操作。算术表达式内可以含有变量（az） 、常量（09）和二元运算符（+，-，*，/，(乘幂)） 。具体实现以下操作：1 以字符序列的形式输入语法正确的前缀表达式并构造表达式。2 用带括弧的中缀表达式输

3、出表达式。3 实现对变量 V 的赋值（V=c） ，变量的初值为 0。4 对算术表达式 E 求值。（二）（二） 系统模块结构设计系统模块结构设计通过对系统功能的分析，基于二叉树表示的算术表达式的功能如图（1）所示。2 图 1：基于二叉树表示的算术表达式的功能图通过上图的功能分析，把整个系统划分为主要的两大个模块：1、 将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列，必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数 BiTree Create(BiTree T)创建二叉树，void Preorder(BiTree T) 先序遍历， void InOrder(BiTree T)

4、中序遍历，void PostOrder(BiTree T) 后序遍历，int Sumleaf(BiTree T) 统计叶结点的数目，int Depth(BiTree T) 二叉树的深度 6 个函数联合来实现；2、 计算中序遍历所得的算术表达式的值。其中先要将扫描得到的中缀表达式转换为后缀表达式，然后利用栈的初始化，进栈与取栈顶元素操作进行对后缀表达式进行计算。该模块借助函数 void InitStack(SeqStack *S)初始化栈，int PushStack(SeqStack *S,char e)进3栈，int GetTop(SeqStack S,char *e)取栈顶元素，void T

5、ranslateExpress(char str,char exp)中缀表达式转后缀表达式，float ComputeExpress(char a)计算后缀表达式的值来实现；三、系统的设计三、系统的设计与实现与实现（一）（一） 二叉树的遍历二叉树的遍历分析：首先构建一棵二叉树，然后依次输出每个遍历的序列。流程图如图 2 所示。图 2：二叉树的遍历流程图该模块的具体代码如下所示：#include#include#define MaxSize 50typedef struct float dataMaxSize; int top; OpStack;typedef struct char dataM

6、axSize; int top; SeqStack;typedef struct BiTNode4char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree 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)/访

7、问根节点 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-r

8、child); 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;5n=Sumleaf(T-rchild);sum=sum+n;return sum;int Depth(BiTree T)/二叉树的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild);depr=Depth(T-rchild);dep

9、=1+(depldepr?depl:depr);return dep;void main()BiTree T;int sum,k;printf(请输入二叉树中的元素(以扩展先序遍历序列输入):n);T=Create(T);printf(先序遍历序列为:);Preorder(T);printf(n);printf(中序遍历序列为:);InOrder(T);printf(n);printf(后序遍历序列为:);PostOrder(T);printf(n);sum=Sumleaf(T);printf(叶结点的数目为:%dn,sum);k=Depth(T);printf(二叉树的深度为:%dn,k);

10、（二）（二） 算术表达式求值算术表达式求值分析：首先初始化一个栈，然后对相关的数据元素及运算符进栈，之后中缀表达式转后缀表达式计算出后缀表达式的值。流程图如图3 所示。6图 3：算术表达式求值流程图该模块的具体代码如下所示：#include#include#include#include#include#define NULL 0#define MaxSize 50typedef struct float dataMaxSize; int top; OpStack;typedef struct char dataMaxSize; int top; SeqStack;void InitStack

11、(SeqStack *S)/初始化栈 S-top=0; int StackEmpty(SeqStack S)/判断栈是否为空 if(S.top =0) return 1; else return 0; int PushStack(SeqStack *S,char e)/进栈 if(S-top=MaxSize) printf(栈已满，不能进栈!); 7return 0; else S-dataS-top=e; S-top+; return 1; int PopStack(SeqStack *S,char *e)/删除栈顶元素 if(S-top=0) printf(栈已空n); return 0;

12、 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+ai-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

13、+; 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-; x2=S.dataS.top; S.top-; result=x1*x2; S.top+; 9S.dataS.top=result; break; case/: x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-;result=x

14、2/x1; S.top+; S.dataS.top=result; break;case:x1=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 !=-1) /如果栈不空，将结果出栈并返回 result=S.dataS.top; S.top-; if(S.top=-1) return result; else printf(表达式错误); exit(-1); return 0; void main()char

15、 aMaxSize,bMaxSize; float f; printf(请输入一个算术表达式:); scanf(%s,&a); printf(中缀表达式为：%sn,a); TranslateExpress(a,b); printf(后缀表达式为：%sn,b); f=ComputeExpress(b); printf(计算结果：%fn,f);四、系统测试四、系统测试（一）（一）测试二叉树遍历函数测试二叉树遍历函数：测试的结果如图 4。图 4： 二叉树的遍历10（二）（二） 测试算术表达式求值函数测试算术表达式求值函数：测试的结果如图 5，6。图 5图 6五、总结五、总结系统完成了对基本的

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

17、ULL 0#define MaxSize 50typedef struct float dataMaxSize; 11int top; OpStack;/存放数字的栈typedef struct char dataMaxSize; int top; SeqStack;/存放运算符的栈typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree Create(BiTree T)/用扩展先序遍历序列创建二叉树 char ch; ch=getchar(); if(ch=0) T=NULL;

18、else T=new BiTNode; T-data=ch; T-lchild=Create(T-lchild); T-rchild=Create(T-rchild); return T;void Visit(char ch)/访问根节点 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);

19、Visit(T-data); InOrder(T-rchild);void PostOrder(BiTree T)/后序遍历 if(T=NULL)return; PostOrder(T-lchild); PostOrder(T-rchild); Visit(T-data); int Sumleaf(BiTree T)/统计叶结点的数目int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)/该结点的左或右分支为空时12 sum+; m=Sumleaf(T-lchild);sum=sum+m; n=Sumleaf(T-rchild);sum=sum+n;r

20、eturn 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(S.top =0) return 1; else return 0; int PushStack(SeqStack *S,char e

21、)/进栈 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; 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!= )

22、 /如果不是空格 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-: 14x1=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-; 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; br