当前位置:首页 >> 数学 >>

算术表达式与二叉树


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

算术表达式与二叉树
一、系统开发的背景
为了方便进行基本的算术运算,减轻对数字较大的数操作时所带来的 麻烦,及其在运算过程中错误的避免。因此设计算术表达式与二叉树的程 序来解决此问题。

二、系统分析与设计
(一) 系统功能要求 由于一个表达式和一棵二叉树之间,存在着自然的对应关系。遍 写一个程序,实现基于二叉树表示的算术表达式的操作。算术表达式 内可以含有变量(a~z) 、常量(0~9)和二元运算符(+,-,*,/, ^(乘幂)) 。 具体实现以下操作: 1 以字符序列的形式输入语法正确的前缀表达式并构造表达式。 2 用带括弧的中缀表达式输出表达式。 3 实现对变量 V 的赋值(V=c) ,变量的初值为 0。 4 对算术表达式 E 求值。

(二) 系统模块结构设计
通过对系统功能的分析,基于二叉树表示的算术表达式的功能 如图(1)所示。

1

图 1:基于二叉树表示的算术表达式的功能图

通过上图的功能分析,把整个系统划分为主要的两大个模块: 1、 将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列, 必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数 BiTree Create(BiTree T)创建二叉树,void Preorder(BiTree T) 先序遍历, void InOrder(BiTree T) 中序遍历,void PostOrder(BiTree T) 后序遍历,int Sumleaf(BiTree T) 统计叶结点的数目,int Depth(BiTree T) 二叉树的深 度 6 个函数联合来实现; 2、 计算中序遍历所得的算术表达式的值。 其中先要将扫描得到的中缀 表达式转换为后缀表达式,然后利用栈的初始化,进栈与取栈顶元素操作 进行对后缀表达式进行计算。 该模块借助函数 void InitStack(SeqStack *S) 初始化栈, PushStack(SeqStack *S,char e)进栈, GetTop(SeqStack int int
2

S,char *e)取栈顶元素,void TranslateExpress(char str[],char exp[]) 中缀表达式转后缀表达式,float ComputeExpress(char a[])计算后缀表 达式的值来实现;

三、系统的设计与实现
(一) 二叉树的遍历
分析:首先构建一棵二叉树,然后依次输出每个遍历的序列。流程图 如图 2 所示。

图 2:二叉树的遍历流程图

该模块的具体代码如下所示:
#include<stdio.h> #include<string.h> #define MaxSize 50 typedef struct { float data[MaxSize]; int top; }OpStack; typedef struct {char data[MaxSize]; int top; }SeqStack; typedef struct BiTNode{

3

char 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)//访问根节点 { 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); 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;

4

n=Sumleaf(T->rchild); sum=sum+n;} return sum; } int Depth(BiTree T)//二叉树的深度 {int dep=0,depl,depr; if(!T) dep=0; else{ depl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?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("叶结点的数目为:%d\n",sum); k=Depth(T); printf("二叉树的深度为:%d\n",k); }

(二) 算术表达式求值
分析:首先初始化一个栈,然后对相关的数据元素及运算符进栈, 之后中缀表达式转后缀表达式计算出后缀表达式的值。 流程图如图 3 所示。

5

图 3:算术表达式求值流程图

该模块的具体代码如下所示:
#include<stdio.h> #include<string.h> #include<malloc.h> #include<stdlib.h> #include<math.h> #define NULL 0 #define MaxSize 50 typedef struct { float data[MaxSize]; int top; }OpStack; typedef struct {char data[MaxSize]; int top; }SeqStack; 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)//进栈 {if(S->top>=MaxSize) { printf("栈已满,不能进栈!");

6

return 0; } else { S->data[S->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->data[S->top]; return 1; } } int GetTop(SeqStack S,char *e)//取栈顶元素 { if(S.top<=0) {printf("栈已空"); return 0; }else {*e=S.data[S.top-1]; return 1; } } void TranslateExpress(char str[],char exp[])//把中缀表达式转换为后缀表达式 {SeqStack S; char ch; char e; int i=0,j=0; InitStack(&S); ch=str[i]; i++; while(ch!='\0') //依次扫描中缀表达式 { switch(ch) { case'(': PushStack(&S,ch); break; case')': while(GetTop(S,&e)&&e!='(') {PopStack(&S,&e); exp[j]=e; j++; } PopStack(&S,&e);break; case'+': case'-': while(!StackEmpty(S)&&GetTop(S,&e)&&e!='(') { PopStack(&S,&e); exp[j]=e; j++; } PushStack(&S,ch);break; case'^': case'*': case'/': while(!StackEmpty(S)&&GetTop(S,&e)&&e=='/'||e=='*'||e=='^') {PopStack(&S,&e); exp[j]=e; j++; }

7

PushStack(&S,ch); break; //是空格就忽略 case' ': break; default: while(ch>='0'&&ch<='9') { exp[j]=ch; j++; ch=str[i]; i++; } i--; exp[j]=' '; j++; } ch=str[i]; i++; } while(!StackEmpty(S)) //将栈中剩余运算符出栈 {PopStack(&S,&e); exp[j]=e; j++; } exp[j]='\0'; } float ComputeExpress(char a[])//计算后缀表达式的值 {OpStack S; int i=0; float x1,x2,value; float result; S.top=-1; while(a[i]!='\0') //依次扫描后缀表达式 { if(a[i]!=' '&&a[i]>='0'&&a[i]<='9')//如果是数字 { value=0; while(a[i]!=' ') //如果不是空格 { value=10*value+a[i]-'0'; i++; } S.top++; S.data[S.top]=value; //处理后进栈 } else //如果是运算符 {switch(a[i]) {case'+': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1+x2; S.top++; S.data[S.top]=result; break; case'-': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x2-x1; S.top++; S.data[S.top]=result; break; case'*': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1*x2; S.top++;

8

S.data[S.top]=result; break; case'/': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x2/x1; S.top++; S.data[S.top]=result; break; case'^': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=float(pow(x1,x2)); S.top++; S.data[S.top]=result; break; } i++; }} if( S.top !=-1) //如果栈不空,将结果出栈并返回 { result=S.data[S.top]; S.top--; if(S.top==-1) return result; else { printf("表达式错误"); exit(-1); } } return 0; } void main() {char a[MaxSize],b[MaxSize]; float f; printf("请输入一个算术表达式:"); scanf("%s",&a); printf("中缀表达式为:%s\n",a); TranslateExpress(a,b); printf("后缀表达式为:%s\n",b); f=ComputeExpress(b); printf("计算结果:%f\n",f);}

四、系统测试
(一) 测试二叉树遍历函数:测试的结果如图 4。

图 4: 二叉树的遍历
9

(二) 测试算术表达式求值函数:测试的结果如图 5,6。

图5

图6

五、总结
系统完成了对基本的数学算术运算的求值的功能。 系统不能对更高一级的复合表达式(如三角函数等)求值,是其不足 之处。 我的收获是经过不断的查询相关的书籍与有关的资料,使得我对原本 不熟的知识有了深刻的了解和认识。也让我能够更加独立的去学习,提高 了我的自主学习的能力。

六、附件(代码、部分图表)
(一) 程序代码:
#include<stdio.h> #include<string.h>//字符串函数 #include<malloc.h>//功能:分配字节的存储区,若内存不够返回 0. #include<stdlib.h>//tandard library 标准库函数头文件,stdlib.h 里面定义了五种类型、 一些宏和通用工具函数 #include<math.h>//数学库函数 #define NULL 0 #define MaxSize 50 typedef struct { float data[MaxSize];

10

int top; }OpStack;//存放数字的栈 typedef struct {char data[MaxSize]; int top; }SeqStack;//存放运算符的栈 typedef struct BiTNode{ char 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)//访问根节点 { 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); Visit(T->data); } int Sumleaf(BiTree T)//统计叶结点的数目 {int sum=0,m,n; if(T){ if((!T->lchild)&&(!T->rchild))//该结点的左或右分支为空时

11

sum++; m=Sumleaf(T->lchild); sum=sum+m; n=Sumleaf(T->rchild); sum=sum+n;} return sum;} int Depth(BiTree T)//二叉树的深度 {int dep=0,depl,depr; if(!T) dep=0; else{ depl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?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)//进栈 {if(S->top>=MaxSize) { printf("栈已满,不能进栈!"); return 0; } else { S->data[S->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->data[S->top]; return 1; } } int GetTop(SeqStack S,char *e)//取栈顶元素 { if(S.top<=0) {printf("栈已空"); return 0; } else {*e=S.data[S.top-1]; return 1; } } void TranslateExpress(char str[],char exp[])//把中缀表达式转换为后缀表达式 {SeqStack S; char ch; char e; int i=0,j=0; InitStack(&S); ch=str[i]; i++; while(ch!='\0') //依次扫描中缀表达式 { switch(ch) { case'(': PushStack(&S,ch); break; case')': while(GetTop(S,&e)&&e!='(') {PopStack(&S,&e); exp[j]=e; j++;} PopStack(&S,&e);break;

12

case'+': case'-': while(!StackEmpty(S)&&GetTop(S,&e)&&e!='(') { PopStack(&S,&e); exp[j]=e; j++; } PushStack(&S,ch);break; case'^': case'*': case'/': while(!StackEmpty(S)&&GetTop(S,&e)&&e=='/'||e=='*'||e=='^') {PopStack(&S,&e); exp[j]=e; j++; } PushStack(&S,ch); break; //是空格就忽略 case' ': break; default: while(ch>='0'&&ch<='9') { exp[j]=ch; j++; ch=str[i]; i++; } i--; exp[j]=' '; j++; } ch=str[i]; i++; } while(!StackEmpty(S)) //将栈中剩余运算符出栈 {PopStack(&S,&e); exp[j]=e; j++; } exp[j]='\0'; } float ComputeExpress(char a[])//计算后缀表达式的值 {OpStack S; int i=0; float x1,x2,value; float result; S.top=-1; while(a[i]!='\0') //依次扫描后缀表达式 { if(a[i]!=' '&&a[i]>='0'&&a[i]<='9')//如果是数字 { value=0; while(a[i]!=' ') //如果不是空格 { value=10*value+a[i]-'0'; i++; } //相当于一个循环,把数组 a[]值赋给 value. S.top++; S.data[S.top]=value; //处理后进栈 } else //如果是运算符 {switch(a[i]) {case'+': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1+x2; S.top++; S.data[S.top]=result; break; case'-':

13

x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x2-x1; S.top++; S.data[S.top]=result; break; case'*': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1*x2; S.top++; S.data[S.top]=result; break; case'/': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x2/x1; S.top++; S.data[S.top]=result; break; case'^': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=float(pow(x1,x2)); S.top++; S.data[S.top]=result; break; } i++; }} if( S.top !=-1) //如果栈不空,将结果出栈并返回 { result=S.data[S.top]; S.top--; if(S.top==-1) return result; else { printf("表达式错误"); exit(-1); } } return 0; } 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("叶结点的数目为:%d\n",sum); k=Depth(T); printf("二叉树的深度为:%d\n",k); char a[MaxSize],b[MaxSize]; float f; printf("请输入一个算术表达式:"); scanf("%s",&a); printf("中缀表达式为:%s\n",a); TranslateExpress(a,b); printf("后缀表达式为:%s\n",b); f=ComputeExpress(b);

14

printf("计算结果:%f\n",f); }

(二) 实验截图:

图 7-a:基于二叉树的算术表达式

图 7-b:基于二叉树的算术表达式

15


相关文章:
算术表达式与二叉树.doc
算术表达式与二叉树 - 目录 一、系统开发的背景 ......
基于二叉树的算术表达式计算与实现.pdf
本文旨在研究表达式向二叉 树的转换,即扫描输入的算术表达式,生成 表达式的二叉树,再以先序遍历此二叉树求 取表达式的值。为由一种算术表达式得出后 缀、前缀两种...
任务书算术表达式与二叉树.doc
任务书算术表达式与二叉树 - 北京理工大学珠海学院计算机学院课程设计 附件 4:
第6章 树和二叉树习题.doc
第6章 树和二叉树习题 - 第六章 树和二叉树 一、选择题 1.算术表达式 a+
2-任务书-算术表达式与二叉树.doc
2-任务书-算术表达式与二叉树 - 北京理工大学珠海学院计算机学院课程设计 附件
基于二叉树的算术表达式计算与实现_图文.pdf
基于二叉树算术表达式计算与实现 - 10. 3969/j. issn. 1001-8972.2012.13.135 ...... ( JZW590112116) 资助 基于二叉树算术表达式计算与实现E valuation ...
算术表达式(例题)-二叉树.doc
算术表达式(例题)-二叉树 - 最早提出遍历问题的是对存储在计算机中的表达式求值
基于二叉树的算术表达式计算与实现_论文.pdf
基于二叉树算术表达式计算与实现 - 算术表达式、栈的操作、二叉树的遍历这几个概念是数据结构教学中的基本内容。算术表达式求值是程序设计语言编译中的一个最基本...
利用二叉树以及栈对算术表达式实现四则运算等计算功能代码.doc
利用二叉树以及栈对算术表达式实现四则运算等计算功能代码 - #include &
树和二叉树习题.doc
和二叉树习题 - 第6章 树和二叉树 一、选择题 1.算术表达式 a+b*(c
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课....doc
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告 - 沈阳理工大学课程设计专用纸 目 题目 录 一.二叉树操作(1)二.算术表达式求 ...
二叉树 算术表达式.txt
二叉树 算术表达式 - /** * 假设输入的中缀表达式为: * (a+b)*(
C语言实现一.二叉树操作 二.用栈实现算术表达式求值 课....pdf
C语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告 - 沈阳理工大学课程设计专用纸 目 题目 录 一.二叉树操作(1)二.算术表达式求...
表达式与二叉树的相互转换_图文.pdf
表达式与二叉树的相互转换 - ISSN 10093044 E-mail:kfy
第6章 树和二叉树习题.doc
第6章 树和二叉树习题 - 第六章 树和二叉树 ) D.abcde*/++ / + * A B C D * E F + G 一、选择题 1.算术表达式 a+b*(c+d/e)转为后缀...
第五章习题_图文.ppt
第五章习题 - 第五章 树和二叉树 习题讨论 一、选择题 1.已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式 为ABC*+DE/-,其前缀形式为( ) A.-A+B...
树和二叉树数据结构实验报告.doc
实习报告题目:编写一个实现基于二叉树表示的算术表达式 Expression 操作程序 班级: 姓名: 学号: 完成日期// 一、 需求分析算术表达式 Expression 内可以含有变量(a...
第6章树和二叉树(2).doc
第六章 树和二叉树 一、选择题 1.算术表达式 a+b*(c+d/e)转为后缀表
...- 第6章 树和二叉树【HSH2013级】给学生.doc
《数据结构》期末复习题及参考答案 - 第6章 树和二叉树【HSH2013级】给学生_...-+A*BC/DE 8、设有一表示算术表达式的二叉树(见下图) , / + * A B C...
数据结构考研复习题第六章--数和二叉树(带答案).doc
数据结构考研复习题第六章--数和二叉树(带答案) - 第六章 树和二叉树 一、选择题 1.已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为 ABC*+DE/-,...
更多相关标签: