表达式求值 二叉树 zstu 08 袁景华.docx
《表达式求值 二叉树 zstu 08 袁景华.docx》由会员分享，可在线阅读，更多相关《表达式求值 二叉树 zstu 08 袁景华.docx（12页珍藏版）》请在冰点文库上搜索。
表达式求值二叉树zstu08袁景华
表达式求值二叉树zstu08袁景华
表达式求值-二叉树-zstu-08-袁景华2010-12-1422：
56一、程序设计的基本思想，原理和算法描述：
表达式建树原理：
对表达式先找到运算级最低的运算操作符，并将其作为该表达式的根结点，
该运算符左右两段表达式分别作为其左右子树。
1.若该运算操作符位于表达式首，则其一定是"-"，此时左子树为空；
2.若该运算操作符是一对括弧（括弧嵌套情况）则化简（把括弧去掉），对表达式构造二叉树；
表达式不合法情况：
1.表达式首为：
"+"、"*"、"/"、"."、"）"；
2.表达式尾为：
"+"、"-"、"*"、"/"、"."、"（"；
表达式合法情况：
1.表达式非首位置：
a."（"之前只能为：
"+"、"-"、"*"、"/"、"（"；
b."）"之前只能为：
"）"、数字"0-9"；
c."+"、"*"、"/"之前只能为：
"）"、数字"0-9"；
d."-"之前只能为：
"（"、"）"、数字"0-9"；
e."."之前只能为：
数字"0-9"；
表达式求值：
将操作数全部转化为double数据类型进行求解。
测试数据：
1.-（（2.5+2.5）/（3-1）*4+（10-8）*6）/（4-2）+（-2*（4+1）/（3-1）*2+1）+12.-（（（（3-1）/2+2.5-（3-4+6））/2-3*2/1）+1.5）*2-3*3/2/（5-3）
3.1000000000*2000000000/44.200.3.3*32.15.99999/116.（45-33）*2-3+4/2*5-37.-（45-33）*2-3+4/2*5-3
二、源程序及注释：
//ExpnBiTree.cpp
#includestdio.h
#includestring.h
#includestdlib.h
#defineSTATUSint
#defineOK1
#defineERROR0
#defineEXP_LEN100//定义表达式的最大长度
#defineDATA_LEN20//定义每个操作数的最大长度
typedefstructBinaryTree
{
intdflag；//标志域，值为1，data存放操作运算符；值为0，data存放操作数
chardata[DATA_LEN+1]；//数据域，存放：
操作运算符或操作数
structBinaryTree*lchild,*rchild；//分别指向结点的左、右子树
}BiTNode,*BiTree；//定义二叉树结点及二叉树类型指针
STATUSCreateBiTree（BiTree&bt,char*p,intl）；
//创建二叉树，并用bt返回树的根地址，p为表达式的首地址，l为表达式的长度
STATUSCalculate（BiTreebt,double&rst）；
//计算表达式的值，bt为据表达式创建的二叉树，用rst返回表达式的值
STATUSPreOrderTraverse（BiTreebt）；//先序遍历二叉树bt，输出先序遍历序列
STATUSInOrderTraverse（BiTreebt）；//中序遍历二叉树bt，输出中序遍历序列
STATUSPostOrderTraverse（BiTreebt）；//后序遍历二叉树bt，输出后序遍历序列
STATUSDestroyBiTree（BiTree&bt）；//销毁二叉树
voidmain（）
{
intn,l,i；//n标志量，值为0，退出程序；l存储表达式的长度；i一般变量
charexpn[EXP_LEN+1]；//存放表达式
doublerst；//存放表达式计算结果
BiTreebt=NULL；//声明一个二叉树
do
{
i=0；
printf（"请输入合法的表达式：
\n"）；
gets（expn）；
for（i=0,l=0；expn[i]！
='[message]'；i++）//去掉表达式中的空格，并计算表达式的长度
if（expn[i]！
=''）expn[l++]=expn[i]；
expn[l]='[message]'；
printf（"正在构建二叉树…\n"）；
if（CreateBiTree（bt,expn,l））printf（"二叉树构建成功！
\n"）；
else
{//销毁未成功建立的二叉树，释放动态申请的内存
printf（"二叉树构建失败！
\n"）；printf（"将销毁二叉树…"）；
if（DestroyBiTree（bt））printf（"二叉树销毁成功！
\n"）；
else{printf（"二叉树销毁失败！
\n"）；exit（0）；}
continue；
}
printf（"即将输出表达式的先序遍历序列…：
\n"）；
PreOrderTraverse（bt）；printf（"\n"）；
printf（"即将输出表达式的中序遍历序列…：
\n"）；
InOrderTraverse（bt）；printf（"\n"）；
printf（"即将输出表达式的后序遍历序列…：
\n"）；
PostOrderTraverse（bt）；printf（"\n"）；
printf（"正在计算表达式的值…：
\n"）；
if（Calculate（bt,rst））printf（"%g\n",rst）；
elseprintf（"计算表达式的值失败！
\n"）；
printf（"即将销毁二叉树…"）；
if（DestroyBiTree（bt））printf（"二叉树销毁成功！
\n"）；
else{printf（"二叉树销毁失败！
\n"）；exit（0）；}
printf（"如果要继续计算下一个表达式，请输入一个非零整数，否则，请输入0：
"）；
scanf（"%d",&n）；getchar（）；
}while（n）；
}
STATUSCreateBiTree（BiTree&bt,char*p,intl）
{
inti=0,lnum=0,rpst1=-1,rpst2=-1,pn=0；
//lnum记录"（"的未成对个数；
//rpst1/rpst2记录表达式中优先级最低的（"*"、"/"）/（"+"、"-"）的位置；
//pn记录操作数中"."的个数,以判断输入操作数是否合法
if（l==0）returnOK；
if（！
（bt=（BiTree）malloc（sizeof（BiTNode））））{printf（"内存申请失败\n"）；returnERROR；}
else
{
bt-lchild=bt-rchild=NULL；
memset（bt-data,'[message]',sizeof（bt-data））；bt-dflag=1；
//默认bt为叶子节点（即，存放操作数）
if（*p=='+'||*p=='*'||*p=='/'||*p=='.'||*p=='）'）//表达式首不合法；
{printf（"表达式输入错误！
\n"）；returnERROR；}
if（！
（*（p+l-1）=='）'||*（p+l-1）='0'&&*（p+l-1）='9'））//表达式尾不合法；
{printf（"表达式输入错误！
\n"）；returnERROR；}
}
if（l==1）//此时只有表达式为数字，表达式才合法
if（*p'0'||*p'9'）{printf（"表达式输入错误！
\n"）；returnERROR；}
else{bt-data[0]=*p；returnOK；}
elseif（l==2）//此时只有表达式为正数或负数，表达式才合法
if（（*p=='-'||*p='0'&&*p='9'）&&*（p+1）='0'&&*（p+1）='9'）
{bt-data[0]=*p；bt-data[1]=*（p+1）；returnOK；}
else{printf（"表达式输入错误！
\n"）；returnERROR；}
else
{
if（*p=='（'）lnum++；
for（i=1；il；i++）
{
if（*（p+i）=='.'）
{
if（！
（*（p+i-1）='0'&&*（p+i-1）='9'））
{printf（"表达式输入错误！
\n"）；returnERROR；}
}
elseif（*（p+i）=='*'||*（p+i）=='/'）
{
if（！
（*（p+i-1）='0'&&*（p+i-1）='9'||*（p+i-1）=='）'））
{printf（"表达式输入错误！
\n"）；returnERROR；}
if（lnum==0）rpst1=i；
}
elseif（*（p+i）=='（'）
{
if（*（p+i-1）=='+'||*（p+i-1）=='-'||*（p+i-1）=='*'||*（p+i-1）=='/'||*（p+i-1）=='（'）
lnum++；
else{printf（"表达式输入错误！
\n"）；returnERROR；}
}
elseif（*（p+i）=='）'）
{
if（*（p+i-1）=='）'||*（p+i-1）='0'&&*（p+i-1）='9'）lnum--；
else{printf（"表达式输入错误！
\n"）；returnERROR；}
if（lnum0）{printf（"表达式输入错误！
\n"）；returnERROR；}
}
elseif（*（p+i）=='+'||*（p+i）=='-'）
{
if（*（p+i）=='+'&&！
（*（p+i-1）='0'&&*（p+i-1）='9'||*（p+i-1）=='）'））
{printf（"表达式输入错误！
\n"）；returnERROR；}
elseif（*（p+i）=='-'&&！
（*（p+i-1）='0'&&*（p+i-1）='9'||*（p+i-1）=='）'||*（p+i-1）=='（'））
{printf（"表达式输入错误！
\n"）；returnERROR；}
if（lnum==0）rpst2=i；
}
}
if（lnum！
=0）{printf（"表达式输入错误！
\n"）；returnERROR；}
//"（"、"）"未能完全配对,表达式输入不合法
if（rpst2-1）
{
bt-dflag=0；bt-data[0]=*（p+rpst2）；
if（CreateBiTree（bt-lchild,p,rpst2））
if（CreateBiTree（bt-rchild,p+rpst2+1,l-rpst2-1））returnOK；
returnERROR；
}
if（rpst10）//此时表明表达式或者是一个数字，或是表达式整体被一对括弧括起来
{
if（*p=='（'）//此时表达式整体被一对括弧括起来
if（CreateBiTree（bt,p+1,l-2））returnOK；
elsereturnERROR；
else
{
if（*（p+1）！
='（'）//此时表达式一定是一个数字
{
for（i=0；il；i++）
{
if（*（p+i）=='.'）pn++；
if（pn1）{printf（"表达式输入错误！
\n"）；returnERROR；}
bt-data[i]=*（p+i）；
}
returnOK；
}
else//此时表达式首一定是操作符"-"，其余部分被一对括弧括起来
{
bt-dflag=0；bt-data[0]='-'；
if（CreateBiTree（bt-rchild,p+2,l-3））returnOK；
elsereturnERROR；
}
}
}
else//此时表明表达式为几个因子想成或相除而组成的
{
bt-dflag=0；bt-data[0]=*（p+rpst1）；
if（CreateBiTree（bt-lchild,p,rpst1））
if（CreateBiTree（bt-rchild,p+rpst1+1,l-rpst1-1））returnOK；
returnERROR；
}
}
}
STATUSCalculate（BiTreebt,double&rst）
{
doublel=0,r=0；//l、r分别存放左右子树所代表的字表达式的值
if（！
bt）{rst=0；returnOK；}
if（bt-dflag==1）{rst=atof（bt-data）；returnOK；}
else
{
if（Calculate（bt-lchild,l））
if（Calculate（bt-rchild,r））
{
switch（bt-data[0]）
{
case'+'：
rst=l+r；break；
case'-'：
rst=l-r；break；
case'*'：
rst=l*r；break；
case'/'：
if（r==0）{printf（"除数为0！
\n"）；returnERROR；}
else{rst=l/r；break；}
default：
returnERROR；
}
//printf（"%g%c%g=%g\n",l,bt-data[0],r,rst）；//输出运算过程
returnOK；
}
returnERROR；
}
}
STATUSPreOrderTraverse（BiTreebt）
{
if（bt）
{
printf（"%s",bt-data）；
if（PreOrderTraverse（bt-lchild））
if（PreOrderTraverse（bt-rchild））returnOK；
returnERROR；
}
returnOK；
}
STATUSInOrderTraverse（BiTreebt）
{
if（bt）
{
if（InOrderTraverse（bt-lchild））
{
printf（"%s",bt-data）；
if（InOrderTraverse（bt-rchild））returnOK；
returnERROR；
}
returnERROR；
}
returnOK；
}
STATUSPostOrderTraverse（BiTreebt）
{
if（bt）
{
if（PostOrderTraverse（bt-lchild））
if（PostOrderTraverse（bt-rchild））
{
printf（"%s",bt-data）；
returnOK；
}
elsereturnERROR；
}
returnOK；
}
STATUSDestroyBiTree（BiTree&bt）
{
if（bt）
{
if（DestroyBiTree（bt-lchild））
if（DestroyBiTree（bt-rchild））
{
free（bt）；
returnOK；
}
elsereturnERROR；
}
returnOK；
}
三、心得与体会：
在考虑建树的如何建树过程中，思考了很长时间，通过和同学交流，
把表达式可能出现的各种情况都注意到，使得建树函数对各种表达式都适用（括弧嵌套，并列）。
考虑到实际情况，需要考虑各种不合法的表达式输入，并作出相应处理。
大家在学习中需要交流；对待每一个问题，要多思考，保证程序严密无错！
希望对大家有帮助，考虑非法表达式输入处理情况较复杂，难免有疏漏之处，如果有什么不妥之处，还请大家指出，谢谢！
经过验证原先的代码有漏洞，故作了更改！
现在应该没什么问题了…
升级会员 