目录
一、系统开发的背景 ................................................................................................................ 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、 将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列，必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数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)初始化栈，int PushStack(SeqStack *S,char e) 进栈，int GetTop(SeqStack
S,char *e)取栈顶元素，void TranslateExpress(char str[],char exp[])中缀表达式转后缀表达式，float ComputeExpress(char a[])计算后缀表达式的值来实现；
三、系统的设计与实现
（一） 二叉树的遍历
分析：首先构建一棵二叉树，然后依次输出每个遍历的序列。流程图如图2所示。
图2：二叉树的遍历流程图
该模块的具体代码如下所示：
#include #include #define MaxSize 50 typedef struct
{ float data[MaxSize]; 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))//该结点的左或右分支为空时 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 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所示。
图3：算术表达式求值流程图
该模块的具体代码如下所示：
#include #include #include #include #include #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("栈已满，不能进栈!");
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
{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++; }
PushStack(&S,ch); break; //是空格就忽略 case' ': break; default:
while(ch>='0'&&ch
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]
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++;
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： 二叉树的遍历
（二） 测试算术表达式求值函数：测试的结果如图5，6。
图
5
图6
五、总结
系统完成了对基本的数学算术运算的求值的功能。
系统不能对更高一级的复合表达式（如三角函数等）求值，是其不足之处。
我的收获是经过不断的查询相关的书籍与有关的资料，使得我对原本不熟的知识有了深刻的了解和认识。也让我能够更加独立的去学习，提高了我的自主学习的能力。
六、附件（代码、部分图表）
(一) 程序代码：
#include
#include//字符串函数
#include//功能：分配字节的存储区，若内存不够返回0.
#include//tandard library标准库函数头文件，stdlib.h 里面定义了五种类型、 一些宏和通用工具函数
#include//数学库函数 #define NULL 0 #define MaxSize 50 typedef struct
{ float data[MaxSize];
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))//该结点的左或右分支为空时
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
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++; }
PushStack(&S,ch); break; //是空格就忽略 case' ': break; default:
while(ch>='0'&&ch
{ 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]
{ 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'-':
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);
printf("计算结果：%f\n",f); }
(二) 实验截图：
图7-a ：基于二叉树的算术表达式
图7-b ：基于二叉树的算术表达式
目录
一、系统开发的背景 ................................................................................................................ 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、 将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列，必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数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)初始化栈，int PushStack(SeqStack *S,char e) 进栈，int GetTop(SeqStack
S,char *e)取栈顶元素，void TranslateExpress(char str[],char exp[])中缀表达式转后缀表达式，float ComputeExpress(char a[])计算后缀表达式的值来实现；
三、系统的设计与实现
（一） 二叉树的遍历
分析：首先构建一棵二叉树，然后依次输出每个遍历的序列。流程图如图2所示。
图2：二叉树的遍历流程图
该模块的具体代码如下所示：
#include #include #define MaxSize 50 typedef struct
{ float data[MaxSize]; 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))//该结点的左或右分支为空时 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 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所示。
图3：算术表达式求值流程图
该模块的具体代码如下所示：
#include #include #include #include #include #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("栈已满，不能进栈!");
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
{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++; }
PushStack(&S,ch); break; //是空格就忽略 case' ': break; default:
while(ch>='0'&&ch
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]
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++;
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： 二叉树的遍历
（二） 测试算术表达式求值函数：测试的结果如图5，6。
图
5
图6
五、总结
系统完成了对基本的数学算术运算的求值的功能。
系统不能对更高一级的复合表达式（如三角函数等）求值，是其不足之处。
我的收获是经过不断的查询相关的书籍与有关的资料，使得我对原本不熟的知识有了深刻的了解和认识。也让我能够更加独立的去学习，提高了我的自主学习的能力。
六、附件（代码、部分图表）
(一) 程序代码：
#include
#include//字符串函数
#include//功能：分配字节的存储区，若内存不够返回0.
#include//tandard library标准库函数头文件，stdlib.h 里面定义了五种类型、 一些宏和通用工具函数
#include//数学库函数 #define NULL 0 #define MaxSize 50 typedef struct
{ float data[MaxSize];
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))//该结点的左或右分支为空时
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
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++; }
PushStack(&S,ch); break; //是空格就忽略 case' ': break; default:
while(ch>='0'&&ch
{ 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]
{ 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'-':
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);
printf("计算结果：%f\n",f); }
(二) 实验截图：
图7-a ：基于二叉树的算术表达式
图7-b ：基于二叉树的算术表达式