湖南大学数据结构四则运算表达式求值实验报告.docx
《湖南大学数据结构四则运算表达式求值实验报告.docx》由会员分享，可在线阅读，更多相关《湖南大学数据结构四则运算表达式求值实验报告.docx（28页珍藏版）》请在冰点文库上搜索。
湖南大学数据结构四则运算表达式求值实验报告
HUNANUNIVERSITY
课程实习报告
题目：
四则运算表达式求值
学生姓名
学生学号
专业班级
指导老师吴帆
完成日期
一、需求分析：
1.本程序要求用户在字符界面上输入一个中缀表达式，回车表示结束。
完成初始化后，把中缀表达式转化为后缀表达式输出，同时输出计算结果。
2.使用二叉树来实现
3.测试数据：
输入：
21+23*（12-6）
输出：
2123126-*+
二、概要设计：
抽象数据类型
利用二叉树后序遍历实现后缀表达式来实现算法。
中缀表达式的存入和读取要用到两个临时的栈一个存操作数，一个存运算符。
利用二叉树，根结点存操作符，其他结点存操作数，利用二叉树的遍历可以方便的存入和读出操作数和运算符。
结点的ADT定义如下：
ADTBinNode
数据对象：
整型
基本操作：
string&element（）;//获取结点的值
stringsetElement（conststring&）;//设置结点的值
BinNode*left（）const;//获取左结点
voidsetLeft（BinNode*）;//设置左结点
BinNode*right（）const;//获取右结点
voidsetRight（BinNode*）;//设置右结点
boolisLeaf（）;//是否是叶子结点
二叉树的ADT：
ADTBinTree
数据对象：
BinNode
基本操作：
boolErrorCheck（stringa）;//表达式错误检测
boolBintreeCreate（stringstr）;//中缀表达式建树
intPrecedence（constchar&）;//运算符op所对应的优先级划定
voidpostOrderTraverse（）;//后序遍历
doublevalue（）{returnval（Root）;}//递归求表达式的值
voidprint（BinNode*）;//打印函数
voiddestroy（BinNode*cur）//后序销毁树
{
if（cur）
{
destroy（cur->lc）;
destroy（cur->rc）;
deletecur;
}
}
doublecacul（doublea,charop,doubleb）//用于计算四则运算的工具函数
{
switch（op）
{
case'+':
returna+b;
case'-':
returna-b;
case'*':
returna*b;
case'/':
returna/b;
}
}
doubleval（BinNode*cur）//在树中递归求值工具函数
{
if（cur->lc==NULL&&cur->rc==NULL）
{
doublen;
strq.clear（）;
strq<<（cur->opnd）;
strq>>n;
returnn;
}
else
returncacul（val（cur->lc）,cur->optr,val（cur->rc））;
}
voidpostOrder（BinNode*p）//后序遍历树的工具函数
{
if（p!
=NULL）{
postOrder（p->lc）;
postOrder（p->rc）;
print（p）;
}
}
ADTStack：
数据对象：
BinNode类型
数据关系：
线性关系
基本操作：
voidpush（constE&it）;//入栈
Epop（）;//出栈
intlength（）const;//栈的大小
constE&topValue（）const;//返回栈顶元素的值
boolempty（）;//是否为空树
算法的基本思想
（1）将中缀表达式转为二叉树
输入表达式
对表达式做错误检测；
中缀建树：
利用两个临时的栈（一个存操作数，一个存运算符），扫描字符串：
.进行括号检测：
遇到左括号则入栈，扫描到的字符为“加、减、乘、除“且不为括号时弹出存操作数栈的栈顶两个操作数和此字符形成一个新的上一层结点并将其重新入栈，检测到右括号时弹出字符栈中的左括号，按此原理依次抵消每对括号；
.遇到数字或小数点继续扫描直到遇到符号为止，取此段扫描到的子串利用stringstream流（头文件）将子串转换成浮点型数据；
.符号优先级比较：
定义在栈中的左括号和栈底字符（此程序中设为‘@’）的优先级最低，比较扫描到的字符和存字符栈的栈顶元素，若栈顶符号的优先级比扫描到的运算符优先级高则弹出存操作数栈的栈顶两个操作数和此字符形成一个结点并将其重新入栈
按此规律依次将每一步运算的结果变成新的上一层结点入栈，最终剩下弹出的则为根结点，最后得到完整二叉树。
（2）利用树的后序遍历提取后缀表达式；
（3）利用树的递归求值：
分别对左右子树递归求出每一步的运算结果覆盖父结点操作数的值，递归返回直至覆盖到根结点，即为表达式的值。
中缀建树：
算法利用两个临时的栈，一个存操作数，一个存操作符，检测到操作数，建立叶子节点，压入存入操作数栈，遇到操作符，存入操作符栈，每次存操作符时与前一个操作符做运算级别比较，若上一个操作符级别大，则弹出上一个操作符，同时弹出两个操作数建立二叉树，操作符做根节点，在把根节点压入操作数栈，括号做优先级最高处理，遇到右括号（前提是有了左括号和必要的运算式），操作符栈弹出，同时弹出两个操作数，建立二叉树，根节点压入操作数的栈。
boolBinTree:
:
BintreeCreate（stringstr）
{
if（str.length（）==0）
{
cout<<"Enterthestringofzhongzhui（EndupwithCR）：
";
cin>>str;
}
if（!
ErrorCheck（str））
{
cout<<"sorry~!
公式有误！
"<return0;
}
else
{
StacknodeStack;
StackopStack;
opStack.push（'@'）;
for（inti=0;i{
switch（str[i]）
{
case'（':
opStack.push（str[i]）;
break;
case'）':
while（Precedence（opStack.topValue（））>0）
nodeStack.push（newBinNode（opStack.pop（）,nodeStack.pop（）,nodeStack.pop（）））;
opStack.pop（）;//弹出栈顶左括号
break;
case'+':
case'-':
case'*':
case'/':
while（Precedence（opStack.topValue（））>=Precedence（str[i]））
nodeStack.push（newBinNode（opStack.pop（）,nodeStack.pop（）,nodeStack.pop（）））;
opStack.push（str[i]）;
break;
default:
//扫描数字
intj;
for（j=i+1;j{
if（str[j]=='+'||str[j]=='-'||str[j]=='*'||str[j]=='/'||str[j]=='）'）
break;
}
nodeStack.push（newBinNode（str.substr（i,j-i）,20））;
i=j-1;
break;
}
}
while（opStack.topValue（）!
='@'）
nodeStack.push（newBinNode（opStack.pop（）,nodeStack.pop（）,nodeStack.pop（）））;
Root=（BinTree*）nodeStack.pop（）;
}
return1;
}
后序遍历提取后缀表达式：
voidBinTree:
:
postOrderTraverse（）
{
cout<<"Thehouzhuistringis:
"<postOrder（Root）;
cout<}
voidpostOrder（BinNode*p）
{
if（p!
=NULL）
{
postOrder（p->lc）;
postOrder（p->rc）;
print（p）;
}
}
递归求值：
doubleval（BinNode*cur）//在树中递归求值工具函数
{
if（cur->lc==NULL&&cur->rc==NULL）
{
doublen;
strq.clear（）;//清空I/O流
strq<<（cur->opnd）;
strq>>n;
returnn;
}
else
returncacul（val（cur->lc）,cur->optr,val（cur->rc））;
}
doublecacul（doublea,charop,doubleb）//用于计算四则运算的工具函数
{
switch（op）
{
case'+':
returna+b;
case'-':
returna-b;
case'*':
returna*b;
case'/':
returna/b;
}
}
程序的流程
程序由五个模块组成：
（1）初始化模块：
完成中缀表达式的输入；
（2）错误检测：
检测中缀表达式输入的合法性；
（3）中缀转换建树模块：
中缀表达式建树，并利用后序遍历输出树；
（4）计算模块：
利用递归计算表达式的值；
（5）输出模块：
输出后缀表达式及计算结果。
三、详细设计：
物理数据类型
用栈存取中缀表达式中的操作符和操作栈：
classStack
{
private:
intsize;
inttop;
float*listArray;
public:
Stack（intsz）
{
size=sz;
top=0;
listArray=newBinNode[size];
}
~Stack（）;
{
delete[]listArray;
}
voidpush（constBinNode&it）//入栈
{
if（top==size）
cout<<"Stackisfull"<listArray[top++]=it;
}
Epop（BinNode&it）//出栈
{
if（top==0）
cout<<"Stackisempty"<returnlistArray[--top];
}
constBinNode&topValue（）const
{
if（top==0）
cout<<"Stackisempty"<returnlistArray[top-1];
}
boolempty（）//是否为空树判断栈是否为空
{
if（top==0）
returntrue;
else
returnfalse;
}
intlength（）const
{
returntop;
}
用结点存操作数、操作符：
classBinNode{
public:
BinNode（char,BinNode*,BinNode*）;
BinNode（string,int）;
~BinNode（）{}
string&element（）;//获取节点的值
stringsetElement（conststring&）;//设置节点的值
BinNode*left（）const;//获取左结点
voidsetLeft（BinNode*）;//设置左结点
BinNode*right（）const;//获取右结点
voidsetRight（BinNode*）;//设置右结点
boolisLeaf（）;//是否是叶子节点
charoptr;//运算符
stringopnd;//操作数
BinNode*lc;
BinNode*rc;
intlen;
};
BinNode:
:
BinNode（charop,BinNode*l,BinNode*r）:
optr（op）,lc（l）,rc（r）{}
BinNode:
:
BinNode（stringm,intleng）:
opnd（m）,lc（NULL）,rc（NULL）,len（leng）{}
string&BinNode:
:
element（）{returnopnd;}
stringBinNode:
:
setElement（conststring&e）{opnd=e;returnopnd;}
inlineBinNode*BinNode:
:
left（）const{returnlc;}
voidBinNode:
:
setLeft（BinNode*b）{lc=（BinNode*）b;}
inlineBinNode*BinNode:
:
right（）const{returnrc;}
voidBinNode:
:
setRight（BinNode*b）{rc=（BinNode*）b;}
boolBinNode:
:
isLeaf（）{return（lc==NULL）&&（rc==NULL）;}
算法的具体步骤
主函数流程图如下：
算法的时空分析
此算法利用栈和二叉树来实现,故次算法的的时间复杂度为Θ（n）。
函数的调用关系图
输入字符串，创建Stack对象
!
ErrorCheck（str）
主程序
switch（str[i]）
BintreeCreate（stringstr）
Root=（BinTree*）nodeStack.pop（）;
postOrderTraverse（）
value（）
输入和输出的格式
输入
Enterthestringofzhongzhui（EndupwithCR）：
//提示
等待输入
输出
Thehouzhuistringis:
//输出表达式结果的位置
Theresultis:
//输出表达式值结果的位置
四、调试分析：
无
五、测试结果:
六、用户使用说明:
1、本程序的运行环境为DOS操作系统，执行文件为szys.exe
2、运行程序时
提示输入
Enterthestringofzhongzhui（EndupwithCR）：
请输入一个中缀表达式（以正整数作为操作数，混合+、-、*、/运算和（），，以回车结束输入）
输出
Thehouzhuistringis:
后缀表达式
Theresultis:
后缀表达式的值
七、实验心得：
这次的实验感觉很难，大致的建树和遍历的大致思想比较好理解，递归求值的效率和简洁度也很令人佩服，难点就在建树过程中括号的检测，出入栈结合叶子结点和分支结点的建立操作起来感觉也有些吃力，还是要巩固对栈、二叉树的掌握，提高编程能力。
八、附录：
//Stack.h
template
classStack
{
public:
Stack（intsz=10）;
~Stack（）;
voidpush（constE&it）;//入栈
Epop（）;//出栈
intlength（）const;
constE&topValue（）const;//返回栈顶元素的值
boolempty（）;//是否为空树
private:
intsize;
inttop;
E*listArray;
};
template
Stack:
:
Stack（intsz）//栈构造函数
{
size=sz;
top=0;
listArray=newE[size];
}
template
Stack:
:
~Stack（）
{
delete[]listArray;
}
template
voidStack:
:
push（constE&it）
{
if（top==size）
cout<<"Stackisfull"<listArray[top++]=it;
}
template
EStack:
:
pop（）
{
if（top==0）
cout<<"Stackisempty"<returnlistArray[--top];
}
template
constE&Stack:
:
topValue（）const
{
if（top==0）
cout<<"Stackisempty"<returnlistArray[top-1];
}
template
intStack:
:
length（）const
{
returntop;
}
template
boolStack:
:
empty（）
{
if（top==0）
returntrue;
else
returnfalse;
}
//BinNode.h
classBinNode{
public:
BinNode（char,BinNode*,BinNode*）;
BinNode（string,int）;
~BinNode（）{}
string&element（）;//获取节点的值
stringsetElement（conststring&）;//设置节点的值
BinNode*left（）const;//获取左结点
voidsetLeft（BinNode*）;//设置左结点
BinNode*right（）const;//获取右结点
voidsetRight（BinNode*）;//设置右结点
boolisLeaf（）;//是否是叶子节点
charoptr;//运算符
stringopnd;//操作数
BinNode*lc;
BinNode*rc;
intlen;
};
BinNode:
:
BinNode（charop,BinNode*l,BinNode*r）:
optr（op）,lc（l）,rc（r）{}
BinNode:
:
BinNode（stringm,intleng）:
opnd（m）,lc（NULL）,rc（NULL）,len（leng）{}
string&BinNode:
:
element（）{returnopnd;}
stringBinNode:
:
setElement（conststring&e）{opnd=e;returnopnd;}
inlineBinNode*BinNode:
:
left（）const{returnlc;}
voidBinNode:
:
setLeft（BinNode*b）{lc=（BinNode*）b;}
inlineBinNode*BinNode:
:
right（）const{returnrc;}
voidBinNode:
:
setRight（BinNode*b）{rc=（BinNode*）b;}
boolBinNode:
:
isLeaf（）{return（lc==NULL）&&（rc==NULL）;}
//BinTree.h
#include"BinNode.h"
#include"Stack.h"
#include
stringstreamstrq;
classBinTree:
publicBinNode
{
public:
BinTree（charop,BinNode*let,BinNode*ret）:
BinNode（op,let,ret）{Root=NULL;}
boolErrorCheck（stringa）;
boolBintreeCreate（stringstr）;//中缀表达式建树
~BinTree（）{destroy（Root）;}
intPrecedence（constchar&）;//返回运算符op所对应的优先级
voidpostOrderTraverse（）;//后序遍历
doublevalue（）{returnval（Root）;}//递归求表达式的值
voidprint（BinNode*）;
private:
BinNode*Root;
voiddestroy（BinNode*cur）
{
if（cur）
{
destroy（cur->lc）;
destroy（cur->rc）;
deletecur;
}
}
doublecacul（doublea,charop,doubleb）//用于计算四则运算的工具函数
{
switch（op）
{
case'+':
returna+b;
case'-':
returna-b;
case'*':
return
升级会员 