数据结构课程设计 实验报告Word文档格式.docx
《数据结构课程设计 实验报告Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计 实验报告Word文档格式.docx（35页珍藏版）》请在冰点文库上搜索。
//获取栈顶元素
intStackEmpty（）;
//测栈空
voidClearStack（）;
//清空栈
voidStackTop（）;
//返回栈顶指针
voidStackTranverse（）;
//显示栈中元素
};
3.算法设计
本题中规定的功能涉及的算法有：
中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。
（1）中缀表达式求值
①首先定义了两个栈，分别用于存取运算符和运算数，如下：
SqStack<
char>
OP（20）;
double>
OD（20）;
②然后依次读取表达式的一个字符C，如果C是运算数，入运算数栈OP.Push（C）；
如果C是运算符，把它与栈顶元素的优先级比较：
若“<
”:
该运算符进栈，读入下一个字符，OP.Push（c）；
若“=”:
运算符退栈，消去一个括号读入下一个字符;
若“>
”，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。
这时需用到比较运算符优先级的函数：
charPrecede（chart1,chart2）
//算符的优先级比较
重复上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果。
算法如下：
case'
<
'
:
OP.Push（c）;
//栈顶元素优先权低
c=*exp++;
break;
='
x=OP.Pop（）;
//脱括号并接收下一字符
>
theta=OP.Pop（）;
//退栈并将运算结果入栈
if（theta=='
（'
||theta=='
）'
）
{
cout<
"
表达式有误!
;
exit（0）;
}
b=OD.Pop（）;
if（b==0）
endl;
if（OD.StackEmpty（））
a=OD.Pop（）;
OD.Push（Operate（a,theta,b））;
}
（2）将中缀表达式转换为后缀表达式
①从左向右读取表达式，读到运算数把它输出；
②读到运算符f2，把运算符栈顶元素的算符优先级f1进行比较：
若“f1<
f2”:
该运算符入运算符栈；
若“f1=f2”:
从运算符栈退出一个运算符，不输出;
若“f1>
f2”，从运算符栈退出一个运算符，从运算数栈里输出所有比f2优先级高的运算符，直至栈顶算符优先级小于f2，f2入运算符栈。
具体算法如下：
case'
c=*exp++;
break;
postexp[i++]=OP.Pop（）;
//运算符出栈输出
（3）将中缀表达式转换为前缀表达式
①将中缀式入栈再依次从栈中读取元素：
如果是操作数把它加入一个数组中;
如果是运算符：
若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素，则此运算符入栈；
否则，栈顶运算符出栈并加入数组中；
若是左括号，栈中元素逐个出栈加入数组中，直到遇到右括号。
②最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到前缀式。
部分算法如下：
SqStack<
ST（20）;
SP（20）;
OP（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=='
-'
*'
/'
））
s[j++]='
'
if（OP.StackEmpty（）||OP.GetTop（）=='
||Precede（x,OP.GetTop（））=='
{
OP.Push（x）;
break;
}
else
s[j++]=OP.Pop（）;
while（OP.GetTop（）!
OP.Pop（）;
OP.StackEmpty（））
s[j++]='
s[j++]=OP.Pop（）;
s[j]='
\0'
while（s[i]!
SP.Push（s[i++]）;
SP.StackEmpty（））
preexp[k++]=SP.Pop（）;
//再次求逆序得到前缀式
（4）后缀表达式求值
①创建一个栈，作为运算数栈
②读取表达式：
若是运算数，入运算数栈；
若是运算符，从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。
③最后，栈顶元素即为表达式的值。
OD（20）;
c=*postexp++;
while（c!
if（（c>
c<
）||c=='
）//为操作数
i=0;
do
z[i++]=c;
c=*postexp++;
}while（c>
||c=='
）;
z[i]='
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是运算符，则从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。
while（*preexp!
ST.Push（*preexp++）;
//利用栈得到前缀表达式的逆序
k=0;
z[k++]=x;
x=ST.Pop（）;
}while（（x>
k--;
for（p=0;
k>
=0;
p++,k--）
s[p]=z[k];
d=atof（s）;
if（In（x））
a=OD.Pop（）;
OD.Push（Operate（a,x,b））;
v=OD.Pop（）;
returnv;
}
（6）界面设计
程序包含多个功能，所以，采用菜单，以方便用户进行功能选择。
菜单如下：
//显示主菜单
cout<
--------*主菜单*-------\n"
1-创建表达式\n"
2-表达式求值\n"
3-求后缀表达式\n"
4-后缀表达式求值\n"
5-求前缀表达式\n"
6-前缀表达式求值\n"
7-显示表达式\n"
8-退出\n"
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<
iostream>
usingnamespacestd;
//顺序栈类实现
T>
SqStack（intm）//创建一个空栈
base=newT[m];
if（base==NULL）
栈创建失败，退出!
exit
（1）;
stacksize=m;
top=-1;
voidSqStack<
Push（Tx）//入栈操作
if（top==stacksize-1）throw"
栈满，无法入栈"
top++;
base[top]=x;
//cout<
top：
top<
TSqStack<
Pop（）//出栈操作
Tx;
if（top==-1）throw"
栈空，不能出栈"
x=base[top--];
returnx;
//获取栈顶元素
GetTop（）
栈空，栈顶无元素"
returnbase[top];
intSqStack<
StackEmpty（）//测栈空
if（top==-1）
return1;
else
return0;
ClearStack（）//清空栈
StackTop（）////返回栈顶指针
cout<
栈顶top="
top;
StackTranverse（）//输出栈中元素
inti=top;
while（i>
=0）
base[i--]<
\t'
charpause;
charPrecede（chart1,chart2）//算符的优先级比较
{
charf;
switch（t2）
case'
if（t1=='
||t1=='
f='
f='
exit（0）;
switch（t1）
f='
cout<
default:
returnf;
intIn（charc）
{//判断c是否为运算符
switch（c）
return1;
return0;
doubleOperate（doublea,chartheta,doubleb）//进行一次运算
doublec;
switch（theta）
c=a+b;
c=a-b;
c=a*b;
c=a/b;
returnc;
doubleVal_Exp（char*exp）//中缀表达式求值
//建立容量为20的运算符栈
//建立容量为20的运算数栈
chartheta;
doublea,b,d;
charc,x;
//存放由键盘接收的字符
charz[6];
//存放符点数字符串
inti;
OP.Push（'
//=是表达式结束标志
//每次从表达式中读取一个字符
x=OP.GetTop（）;
||x!
if（In（c））//是7种运算符之一
switch（Precede（x,c））
OD.Push（Operate（a,theta,b））;
elseif（c>
）//c是操作数
i=0;
do
z[i]=c;
i++;
}while（c>
z[i]='
d=atof（z）;
//将字符串数组转为符点型存于d
OD.Push（d）;
else//c是非法字符
d=OD.GetTop（）;
returnd;
voidCreatePreExp（char*exp,char*&
preexp）//由中缀式求前缀式
{
charx;
chars[20];
intj=0,i=0,k=0;
）//利用栈得到中缀式的逆序
preexp[k]='
前缀表达式为:
preexp<
voidCreatePostExp（char*exp,char*&
postexp）
{//由中缀式求后缀式
charc,x;
inti=0;
while（c）
postexp[i++]=c;
c=*exp++;
if（In（c））//是7种运算符之一
postexp[i++]='
x=OP.GetTop（）;
switch（Precede（x,c））
case'
break;
postexp[i]='
}//while
后缀表达式为:
postexp<
doubleVal_PostExp（char*postexp）//后缀表达式求值
升级会员 