数据结构课程设计 实验报告.docx
《数据结构课程设计 实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计 实验报告.docx（35页珍藏版）》请在冰点文库上搜索。
数据结构课程设计实验报告
数据结构课程设计实验报告
题目：
2.3表达式求值问题
1.问题描述
表达式是数据运算的基本形式。
人们的书写习惯是中缀式，如：
11+22*（7-4）/3。
中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。
表达式还有后缀式（如：
2274—*3/11+）和前缀式（如：
+11/*23—743）。
后缀表达式和前缀表达式中没有括号，给计算带来方便。
如后缀式计算时按运算符出现的先后进行计算。
本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。
2.数据结构设计
本题中使用顺序栈用来存取运算符和运算数，顺序栈类的定义如下：
//顺序栈类定义
template
classSqStack
{
private:
T*base;//栈底指针
inttop;//栈顶
intstacksize;//栈容量
public:
SqStack（intm）;//构建函数
~SqStack（）{delete[]base;top=0;stacksize=0;}//析构函数
voidPush（Tx）;//入栈
TPop（）;//出栈
TGetTop（）;//获取栈顶元素
intStackEmpty（）;//测栈空
voidClearStack（）;//清空栈
voidStackTop（）;//返回栈顶指针
voidStackTranverse（）;//显示栈中元素
};
3.算法设计
本题中规定的功能涉及的算法有：
中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。
（1）中缀表达式求值
①首先定义了两个栈，分别用于存取运算符和运算数，如下：
SqStackOP（20）;
SqStackOD（20）;
②然后依次读取表达式的一个字符C，如果C是运算数，入运算数栈OP.Push（C）；
如果C是运算符，把它与栈顶元素的优先级比较：
若“<”:
该运算符进栈，读入下一个字符，OP.Push（c）；若“=”:
运算符退栈，消去一个括号读入下一个字符;
若“>”，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。
这时需用到比较运算符优先级的函数：
charPrecede（chart1,chart2）
//算符的优先级比较
重复上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果。
算法如下：
case'<':
OP.Push（c）;//栈顶元素优先权低
c=*exp++;
break;
case'=':
x=OP.Pop（）;//脱括号并接收下一字符
c=*exp++;
break;
case'>':
theta=OP.Pop（）;//退栈并将运算结果入栈
if（theta=='（'||theta=='）'）
{
cout<<"表达式有误!
";
exit（0）;
}
b=OD.Pop（）;
if（b==0）
{
cout<<"表达式有误!
"<exit（0）;
}
if（OD.StackEmpty（））
{
cout<<"表达式有误!
"<exit（0）;
}
a=OD.Pop（）;
OD.Push（Operate（a,theta,b））;
}
（2）将中缀表达式转换为后缀表达式
①从左向右读取表达式，读到运算数把它输出；
②读到运算符f2，把运算符栈顶元素的算符优先级f1进行比较：
若“f1该运算符入运算符栈；
若“f1=f2”:
从运算符栈退出一个运算符，不输出;
若“f1>f2”，从运算符栈退出一个运算符，从运算数栈里输出所有比f2优先级高的运算符，直至栈顶算符优先级小于f2，f2入运算符栈。
具体算法如下：
case'<':
OP.Push（c）;//栈顶元素优先权低
c=*exp++;break;
case'=':
x=OP.Pop（）;//脱括号并接收下一字符
c=*exp++;break;
case'>':
postexp[i++]=OP.Pop（）;break;//运算符出栈输出
（3）将中缀表达式转换为前缀表达式
①将中缀式入栈再依次从栈中读取元素：
如果是操作数把它加入一个数组中;
如果是运算符：
若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素，则此运算符入栈；否则，栈顶运算符出栈并加入数组中；
若是左括号，栈中元素逐个出栈加入数组中，直到遇到右括号。
②最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到前缀式。
部分算法如下：
SqStackST（20）;
SqStackSP（20）;
SqStackOP（20）;
while（*exp!
='='）//利用栈得到中缀式的逆序
ST.Push（*exp++）;
while（!
ST.StackEmpty（））
{
x=ST.Pop（）;
if（（x>='0'&&x<='9'）||x=='.'）
{
s[j++]=x;
}
if（x=='）'）
OP.Push（x）;
while（（x=='+'）||（x=='-'）||（x=='*'）||（x=='/'））
{
s[j++]='';
if（OP.StackEmpty（）||OP.GetTop（）=='）'||Precede（x,OP.GetTop（））=='>'||Precede（x,OP.GetTop（））=='='）
{
OP.Push（x）;
break;
}
else
s[j++]=OP.Pop（）;
}
if（x=='（'）
{
while（OP.GetTop（）!
='）'）
s[j++]=OP.Pop（）;
OP.Pop（）;
}
}
while（!
OP.StackEmpty（））
{
s[j++]='';
s[j++]=OP.Pop（）;
}
s[j]='\0';
while（s[i]!
='\0'）
{
SP.Push（s[i++]）;
}
while（!
SP.StackEmpty（））
preexp[k++]=SP.Pop（）;//再次求逆序得到前缀式
（4）后缀表达式求值
①创建一个栈，作为运算数栈
②读取表达式：
若是运算数，入运算数栈；
若是运算符，从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。
③最后，栈顶元素即为表达式的值。
具体算法如下：
SqStackOD（20）;
c=*postexp++;
while（c!
='\0'）
{
if（（c>='0'&&c<='9'）||c=='.'）//为操作数
{
i=0;
do
{
z[i++]=c;
c=*postexp++;
}while（c>='0'&&c<='9'||c=='.'）;
z[i]='\0';
d=atof（z）;//将字符串数组转为浮点型存于d
OD.Push（d）;
}
if（In（c））//c为运算符
{
b=OD.Pop（）;//退出两个运算数运算
a=OD.Pop（）;
OD.Push（Operate（a,c,b））;
c=*postexp++;
}
c=*postexp++;
}
v=OD.Pop（）;
（5）前缀表达式求值
①创建栈ST和栈OD用于存取表达式逆序和运算数，
利用栈得到前缀表达式的逆序存入栈ST；
②栈ST出栈，为X:
若X是运算数，则把X存入数组，直至X不是运算数；
若X是运算符，则从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。
③最后，栈顶元素即为表达式的值。
具体算法如下：
SqStackST（20）;
SqStackOD（20）;
while（*preexp!
='\0'）
{
ST.Push（*preexp++）;//利用栈得到前缀表达式的逆序
}
while（!
ST.StackEmpty（））
{
x=ST.Pop（）;
if（（x>='0'&&x<='9'）||x=='.'）
{
k=0;
do
{
z[k++]=x;
x=ST.Pop（）;
}while（（x>='0'&&x<='9'）||x=='.'）;
k--;
for（p=0;k>=0;p++,k--）
s[p]=z[k];
d=atof（s）;
OD.Push（d）;
}
if（In（x））
{
a=OD.Pop（）;
b=OD.Pop（）;
OD.Push（Operate（a,x,b））;
}
}
v=OD.Pop（）;
returnv;
}
（6）界面设计
程序包含多个功能，所以，采用菜单，以方便用户进行功能选择。
菜单如下：
//显示主菜单
cout<<"--------*主菜单*-------\n";
cout<<"1-创建表达式\n";
cout<<"2-表达式求值\n";
cout<<"3-求后缀表达式\n";
cout<<"4-后缀表达式求值\n";
cout<<"5-求前缀表达式\n";
cout<<"6-前缀表达式求值\n";
cout<<"7-显示表达式\n";
cout<<"8-退出\n";
cout<<"Enterchoice:
";
4.运行与测试
（1）运行程序，显示菜单，如下图所示：
（2）按“1”创建表达式。
根据提示，输入表达式，如下图所示：
（3）按“2”表达式求值。
（4）按“3”求后缀表达式。
（5）按“4”求后缀表达式的值。
（6）按“5”求前缀表达式。
（7）按“6”求前缀表达式的值。
（8）按“7”求显示中缀表达式。
（9）按“1”和“2”，输入一个错误的表达式，程序会判断表达式错误。
（10）按“8”退出。
5.调试记录及收获
（1）学会理解运用栈的结构，使用栈的“先进后出”的特点；
（2）前缀和后缀的变换借助于栈实现，理解前缀、中缀、后缀的不同之处；
（3）调试程序要细致耐心，当程序的功能较多时，要仔细测试程序的每一个功能，发现错误要及时查错修改，不断完善程序。
7.源程序
#include
usingnamespacestd;
//顺序栈类定义
template
classSqStack
{
private:
T*base;//栈底指针
inttop;//栈顶
intstacksize;//栈容量
public:
SqStack（intm）;//构建函数
~SqStack（）{delete[]base;top=0;stacksize=0;}//析构函数
voidPush（Tx）;//入栈
TPop（）;//出栈
TGetTop（）;//获取栈顶元素
intStackEmpty（）;//测栈空
voidClearStack（）;//清空栈
voidStackTop（）;//返回栈顶指针
voidStackTranverse（）;//显示栈中元素
};
//顺序栈类实现
template
SqStack:
:
SqStack（intm）//创建一个空栈
{
base=newT[m];
if（base==NULL）
{
cout<<"栈创建失败，退出!
"<exit
（1）;
}
stacksize=m;
top=-1;
}
template
voidSqStack:
:
Push（Tx）//入栈操作
{
if（top==stacksize-1）throw"栈满，无法入栈";
top++;
base[top]=x;
//cout<<"top：
"<}
template
TSqStack:
:
Pop（）//出栈操作
{
Tx;
if（top==-1）throw"栈空，不能出栈";
x=base[top--];
//cout<<"top：
"<returnx;
}
template//获取栈顶元素
TSqStack:
:
GetTop（）
{
if（top==-1）throw"栈空，栈顶无元素";
//cout<<"top：
"<returnbase[top];
}
template
intSqStack:
:
StackEmpty（）//测栈空
{
if（top==-1）
return1;
else
return0;
}
template
voidSqStack:
:
ClearStack（）//清空栈
{
top=-1;
}
template
voidSqStack:
:
StackTop（）////返回栈顶指针
{
cout<<"栈顶top="<}
template
voidSqStack:
:
StackTranverse（）//输出栈中元素
{
inti=top;
while（i>=0）
cout<cout<}
charpause;
charPrecede（chart1,chart2）//算符的优先级比较
{
charf;
switch（t2）
{
case'+':
case'-':
if（t1=='（'||t1=='='）
f='<';
else
f='>';
break;
case'*':
case'/':
if（t1=='*'||t1=='/'||t1=='）'）
f='>';
else
f='<';
break;
case'（':
if（t1=='）'）
{
cout<<"表达式有误!
"<exit（0）;
}
else
f='<';
break;
case'）':
switch（t1）
{
case'（':
f='=';
break;
case'=':
cout<<"表达式有误!
"<exit（0）;
default:
f='>';
}
break;
case'=':
switch（t1）
{
case'=':
f='=';
break;
case'（':
cout<<"表达式有误!
"<exit（0）;
default:
f='>';
}
}
returnf;
}
intIn（charc）
{//判断c是否为运算符
switch（c）
{
case'+':
case'-':
case'*':
case'/':
case'（':
case'）':
case'=':
return1;
default:
return0;
}
}
doubleOperate（doublea,chartheta,doubleb）//进行一次运算
{
doublec;
switch（theta）
{
case'+':
c=a+b;break;
case'-':
c=a-b;break;
case'*':
c=a*b;break;
case'/':
c=a/b;break;
}
returnc;
}
doubleVal_Exp（char*exp）//中缀表达式求值
{
SqStackOP（20）;//建立容量为20的运算符栈
SqStackOD（20）;//建立容量为20的运算数栈
chartheta;
doublea,b,d;
charc,x;//存放由键盘接收的字符
charz[6];//存放符点数字符串
inti;
OP.Push（'='）;//=是表达式结束标志
c=*exp++;//每次从表达式中读取一个字符
x=OP.GetTop（）;
while（c!
='='||x!
='='）
{
if（In（c））//是7种运算符之一
switch（Precede（x,c））
{
case'<':
OP.Push（c）;//栈顶元素优先权低
c=*exp++;
break;
case'=':
x=OP.Pop（）;//脱括号并接收下一字符
c=*exp++;
break;
case'>':
theta=OP.Pop（）;//退栈并将运算结果入栈
if（theta=='（'||theta=='）'）
{
cout<<"表达式有误!
";
exit（0）;
}
b=OD.Pop（）;
if（b==0）
{
cout<<"表达式有误!
"<exit（0）;
}
if（OD.StackEmpty（））
{
cout<<"表达式有误!
"<exit（0）;
}
a=OD.Pop（）;
OD.Push（Operate（a,theta,b））;
}
elseif（c>='0'&&c<='9'||c=='.'）//c是操作数
{
i=0;
do
{
z[i]=c;
i++;
c=*exp++;
}while（c>='0'&&c<='9'||c=='.'）;
z[i]='\0';
d=atof（z）;//将字符串数组转为符点型存于d
OD.Push（d）;
}
else//c是非法字符
{
cout<<"表达式有误!
"<exit（0）;
}
x=OP.GetTop（）;
}
d=OD.GetTop（）;
returnd;
}
voidCreatePreExp（char*exp,char*&preexp）//由中缀式求前缀式
{
charx;
chars[20];
intj=0,i=0,k=0;
SqStackST（20）;
SqStackSP（20）;
SqStackOP（20）;
while（*exp!
='='）//利用栈得到中缀式的逆序
ST.Push（*exp++）;
while（!
ST.StackEmpty（））
{
x=ST.Pop（）;
if（（x>='0'&&x<='9'）||x=='.'）
{
s[j++]=x;
}
if（x=='）'）
OP.Push（x）;
while（（x=='+'）||（x=='-'）||（x=='*'）||（x=='/'））
{
s[j++]='';
if（OP.StackEmpty（）||OP.GetTop（）=='）'||Precede（x,OP.GetTop（））=='>'||Precede（x,OP.GetTop（））=='='）
{
OP.Push（x）;
break;
}
else
s[j++]=OP.Pop（）;
}
if（x=='（'）
{
while（OP.GetTop（）!
='）'）
s[j++]=OP.Pop（）;
OP.Pop（）;
}
}
while（!
OP.StackEmpty（））
{
s[j++]='';
s[j++]=OP.Pop（）;
}
s[j]='\0';
while（s[i]!
='\0'）
{
SP.Push（s[i++]）;
}
while（!
SP.StackEmpty（））
preexp[k++]=SP.Pop（）;//再次求逆序得到前缀式
preexp[k]='\0';
cout<<"前缀表达式为:
"<}
voidCreatePostExp（char*exp,char*&postexp）
{//由中缀式求后缀式
charc,x;
inti=0;
SqStackOP（20）;
OP.Push（'='）;//=是表达式结束标志
c=*exp++;
while（c）
{
if（（c>='0'&&c<='9'）||c=='.'）
{
postexp[i++]=c;
c=*exp++;
}
if（In（c））//是7种运算符之一
{
postexp[i++]='';
x=OP.GetTop（）;
switch（Precede（x,c））
{
case'<':
OP.Push（c）;//栈顶元素优先权低
c=*exp++;
break;
case'=':
x=OP.Pop（）;//脱括号并接收下一字符
c=*exp++;
break;
case'>':
postexp[i++]=OP.Pop（）;//运算符出栈输出
break;
}
}
postexp[i]='\0';
}//while
cout<<"后缀表达式为:
"<}
doubleVal_PostExp（char*postexp）//后缀表达式求值
{
升级会员 