7A版四则运算表达式求值实验报告.docx
《7A版四则运算表达式求值实验报告.docx》由会员分享，可在线阅读，更多相关《7A版四则运算表达式求值实验报告.docx（11页珍藏版）》请在冰点文库上搜索。
7A版四则运算表达式求值实验报告
HUNANUNIVERSITY
课程实习报告
题目：
四则运算表达式求值
学生姓名：
学生学号：
专业班级：
指导老师：
完成日期：
一、需求分析
四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。
本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。
在字符界面上输入一个中缀表达式，回车表示结束。
如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
测试数据
输入：
21+23G（12-6）
输出：
2123126-G+
二、详细设计
输入和输出的格式
输入
本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式
输出
后缀表达式为：
//输出结果的位置
表达式的值为：
//输出结果的位置
三、调试分析
本次实验的难点主要是在建立二叉树的问题上。
关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。
因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。
另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。
四、测试结果
五、用户使用说明（可选）
1、运行程序时
提示输入四则运算表达式
本程序可以将中缀表达式转化为后缀表达式，并计算结果
请输入四则运算表达式：
输出
后缀表达式为：
表达式的值为：
程序源代码（c++）
#include
#include
#include
#include
constintMaG=100;
usingnamespacestd;
classNode{
public:
charch[MaG];//考虑到数值有时会是两位数，所以使用字符串数组
NodeGlChild;
NodeGrChild;
Node（）{
strcpy（ch,""）;
lChild=rChild=NULL;
}
~Node（）{
if（lChild!
=NULL）
deletelChild;
if（rChild!
=NULL）
deleterChild;
}
};
staticintcount=0;
staticchararray[MaG];//保存原始的中缀表达式
staticcharstr[2GMaG];//保存后序遍历出来的字符串，为表达式求值提供方便
staticintk=0;
chargetOp（NodeGtemp）;//temp指针保存每个结点，返回的是运算符
NodeGcrtTree（NodeGroot）;//传入根结点指针，返回根结点指针
voidoutput（NodeGroot）;//获得处理后的字符串
boolisError（char）;//判断字符是否有问题
voiddeal（）;//对字符数组进行处理
doublevalue（string）;//计算后缀表达式，得到其结果。
intmain（）{
NodeGroot=NULL;
cout<<"输入中缀表达式：
";
cin.getline（array,40）;
deal（）;
root=crtTree（root）;
cout<<"输出后缀表达式：
";
output（root）;
cout<cout<<"输出后缀表达式的值：
";
if（value（str）!
=0）
cout<（2）<else
cout<<"AWrongInput!
"<return0;
}
//将数字字符存入一个结点，并返回数字字符的后一个符号
chargetOp（NodeGtemp）{
inti=0;
if（isError（array[count]））
eGit（0）;
while（array[count]<='9'&&array[count]>='0'||array[count]=='.'）{
temp->ch[i]=array[count];
i++;
count++;
}
temp->ch[i]='\0';
count++;
returnarray[count-1];
}
//传入根结点指针，返回根结点指针
NodeGcrtTree（NodeGroot）{
NodeGp,Gq;
charop;
if（root==NULL）{
root=newNode;
p=newNode;
}
op=getOp（root）;
while（op!
='='）{
q=newNode;
q->ch[0]=op;
q->ch[1]='\0';
switch（op）
{
case'+':
case'-':
q->lChild=root;
root=q;
p=newNode;
op=getOp（p）;
root->rChild=p;
break;
case'G':
case'/':
if（root->ch[0]=='+'||root->ch[0]=='-'）{
p=newNode;
strcpy（p->ch,root->ch）;
p->lChild=root;
p->rChild=q;
op=getOp（root）;
root=p;
}else{
q->lChild=root;
root=q;
p=newNode;
op=getOp（p）;
root->rChild=p;
}break;
case'（':
p=root;
while（p->rChild）
p=p->rChild;
if（p->lChild==NULL）{
p->lChild=crtTree（p->lChild）;//递归创建括号里的指针
op=array[count];
count++;
break;
}else{
p->rChild=crtTree（p->rChild）;//递归创建括号里的指针
op=array[count];
count++;
break;
}
case'）':
returnroot;
}
}
returnroot;
}
//传入根结点，后序遍历,赋值给另一个字符数组（主要是为了给后序的计算表达式值提供方便）
voidoutput（NodeGroot）{
intn;
if（root）{
output（root->lChild）;
output（root->rChild）;
n=0;
while（root->ch[n]!
='\0'）
str[k++]=root->ch[n++];
str[k++]='';
}
}
boolisError（charch）{//判断每个字符是否有错
if（ch!
='+'&&ch!
='-'&&ch!
='G'&&ch!
='/'&&!
（ch<='9'&&ch>='0'）&&ch!
='.'&&ch!
='（'&&ch!
='）'）{
cout<<"字符错误！
";
returntrue;
}
returnfalse;
}
voiddeal（）{//对字符数组进行处理
inti=0,n=0;
while（array[i]）{
if（array[i]==''||array[i]=='='）
i++;
array[n++]=array[i++];
}
array[n++]='=';
array[n]='\0';
}
doublevalue（strings2）{//计算后缀表达式，得到其结果。
stacks;
doubleG,y;
inti=0;
while（iif（s2[i]==''）
i++;
switch（s2[i]）
{
case'+':
if（s.size（）>=2）{
G=s.top（）;s.pop（）;G+=s.top（）;s.pop（）;i++;break;
}
else
return0;
case'-':
if（s.size（）>=2）{
G=s.top（）;s.pop（）;G=s.top（）-G;s.pop（）;i++;break;
}
else
return0;
case'G':
if（s.size（）>=2）{
G=s.top（）;s.pop（）;GG=s.top（）;s.pop（）;i++;break;
}
else
return0;
case'/':
if（s.size（）>=2）{
if（s.top（）==0）return0;
else{
G=s.top（）;s.pop（）;G=s.top（）/G;s.pop（）;i++;break;
}
}
else
return0;
default:
G=0;
while（'0'<=s2[i]&&s2[i]<='9'）{
G=GG10+s2[i]-'0';
i++;
}
if（s2[i]=='.'）{
doublek=10.0;
y=0;
i++;
while（'0'<=s2[i]&&s2[i]<='9'）{
y+=（（s2[i]-'0'）/k）;
i++;
kG=10;
}
G+=y;
}
break;
}
if（G!
=0）
s.push（G）;
}
if（s.size（）==1）
returns.top（）;
else
return0;
}
六、实验结论
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
升级会员 