综合实验六利用栈实现表达式求解.docx
《综合实验六利用栈实现表达式求解.docx》由会员分享，可在线阅读，更多相关《综合实验六利用栈实现表达式求解.docx（10页珍藏版）》请在冰点文库上搜索。
综合实验六利用栈实现表达式求解
综合实验六利用栈实现表达式求解
一、实验名称
利用栈实现表达式求解
二、实验目的
1、熟悉并栈的数据结构的实现与操作
2、掌握栈的典型应用—利用栈实现表达式求解
三、实验内容及要求：
实验内容
问题描述：
输入一个表达式，按如下要求完成其求值运算：
（1）表达式中允许有两种括号：
（、）、[、]，请验证其匹配成对的合法性
（2）运算符限定于加减乘除四种运算，请验证表达式是否书写合法，如：
3+2-*5就不是一个合法表达式。
（3）使用栈的原理实现表达式求值。
（4）尽量考虑参与运算的数是非1位数，如：
234+32*12
根据以上问题给出的以下存储结构定义：
#definestack_init_size100//定义栈的最大初始化容量
#definestackincreament10//定义栈的增量
#defineoverflow-2
typedefstruct{
char*base;
char*top;
intstacksize;
}Sqstackcha;//定义存放运算符号的栈的数据类型。
typedefstruct{
double*base;
double*top;
intstacksize;
}Sqstackdou;//定义存放操作数或中间结果的栈的数据类型、。
Sqstackchaoptr;
Sqstackdouopnd;
――――――――――定义基本操作的函数说明―――――――――――――
chargettop（Sqstackcha&s）;//取操作符栈顶元素
doublegettop（Sqstackdou&s）;;//取操作数栈顶元素
intprecede（Sqstackcha&s,charc）;//比较字符c与操作符栈顶元素的优先级
voidinitstack（Sqstackcha&s）;//初始化操作符栈
voidinitstack（Sqstackdou&s）;//初始化操作数栈
doubleopterate（doublea,chartheta,doubleb）;//对操作数a和b用操作符运行其结果
voidpush（Sqstackcha&s,chare）;//操作符入栈
voidpush（Sqstackdou&s,doublee）;//操作数入栈
charpop（Sqstackcha&s,chare）;//操作符出栈
doublepop（Sqstackdou&s,doublee）;//操作符出栈
实验要求
（1）、用C语言编程实现上述实验内容中的结构定义和算法。
（2）、要有main（）函数，并且在main（）函数中使用检测数据调用上述算法。
（3）、实验完成后撰写实验报告，实验报告的具体格式参见《实验报告须知》。
（4）、实验完成后把打印好的实验报告以及电子版的实验报告和源程序一并上交。
参考源代码：
#include
#include
#definestack_init_size100//定义栈的最大初始化容量
#definestackincreament10//定义栈的增量
#defineoverflow-2
typedefstruct{
char*base;
char*top;
intstacksize;
}Sqstackcha;//定义存放运算符号的栈的数据类型。
typedefstruct{
double*base;
double*top;
intstacksize;
}Sqstackdou;//定义存放操作数或中间结果的栈的数据类型、。
Sqstackchaoptr;
Sqstackdouopnd;
//******************************************
chargettop（Sqstackcha&s）;
doublegettop（Sqstackdou&s）;
intprecede（Sqstackcha&s,charc）;
voidinitstack（Sqstackcha&s）;
voidinitstack（Sqstackdou&s）;
doubleopterate（doublea,chartheta,doubleb）;
voidpush（Sqstackcha&s,chare）;
voidpush（Sqstackdou&s,doublee）;
charpop（Sqstackcha&s,chare）;
doublepop（Sqstackdou&s,doublee）;
voidinitstack（Sqstackcha&s）
//初始化字符型栈
{
s.base=（char*）malloc（stack_init_size*sizeof（char））;
if（!
s.base）
{
cout<<"e";
exit（overflow）;
}
s.top=s.base;
s.stacksize=stack_init_size;
}
voidinitstack（Sqstackdou&s）
//初始化double型栈
{
s.base=（double*）malloc（stack_init_size*sizeof（double））;
if（!
s.base）exit（overflow）;
s.top=s.base;
s.stacksize=stack_init_size;
}
voidpush（Sqstackcha&s,chare）
//操作符栈操作。
{
if（s.top-s.base>=s.stacksize）{
s.base=（char*）realloc（s.base,
（s.stacksize+stackincreament）*sizeof（char））;
if（!
s.base）exit（overflow）;
s.stacksize+=stackincreament;
}
*s.top++=e;
}
voidpush（Sqstackdou&s,doublee）
//操作数进栈操作。
{
if（s.top-s.base>=s.stacksize）{
s.base=（double*）realloc（s.base,
（s.stacksize+stackincreament）*sizeof（double））;
if（!
s.base）{
exit（overflow）;
}
s.stacksize+=stackincreament;
}
*s.top++=e;
}
chargettop（Sqstackcha&s）
//取操作符栈栈顶元素
{
chare;
if（s.top==s.base）{
exit（overflow）;
}
e=*（s.top-1）;
returne;
}
doublegettop（Sqstackdou&s）
//取操作数栈栈顶元素
{
doublee;
if（s.top==s.base）{
exit（overflow）;
}
e=*（s.top-1）;
returne;
}
//********************************************
charpop（Sqstackcha&s,chare）
//操作符出栈操作
{
if（s.top==s.base）{
cout<<"e";
exit（overflow）;
}
e=*--s.top;
returne;
}
doublepop（Sqstackdou&s,doublee）
//操作数出栈操作
{
if（s.top==s.base）{
exit（overflow）;
}
e=*--s.top;
returne;
}
intprecede（Sqstackcha&s,charc）
//对运算符优先级的判断函数
{
intflag;
chara1;
a1=gettop（optr）;
switch（a1）{
case'+':
if（c=='*'||c=='/'||c=='（'）
flag=-1;
else
if（c=='+'||c=='-'||c=='）'||c=='#'）
flag=1;
break;
case'-':
if（c=='*'||c=='/'||c=='（'）
flag=-1;
else
if（c=='+'||c=='-'||c=='）'||c=='#'）
flag=1;
break;
case'*':
if（c=='（'）
flag=-1;
else
if（c=='+'||c=='-'||c=='*'||c=='/'||c=='）'||c=='#'）
flag=1;
break;
case'/':
if（c=='（'）
flag=-1;
else
flag=1;
break;
case'（':
if（c=='）'）
flag=0;
else
if（c=='#'）{
cout<<"输入的表达式不正确！
"<exit（0）;
}
else
flag=-1;
break;
case'）':
if（c=='（'）
{
cout<<"输入的表达式不正确！
"<exit（0）;
}
else
flag=1;
break;
case'#':
if（c=='#'）
flag=0;
else
if（c=='）'）{
cout<<"输入的表达式不正确！
"<exit（0）;
}
else
flag=-1;
break;
}
returnflag;
}
doubleopterate（doublea,chartheta,doubleb）
//double型数之间的基本运算函数
{
doublec;
switch（theta）{
case'+':
c=a+b;
break;
case'-':
c=a-b;
break;
case'*':
c=a*b;
break;
case'/':
c=a/b;
break;
}
returnc;
}
//主函数。
voidmain（）{
doublex,y,z,a,b;
charr,theta,s;
cout<<"请输入计算表达式并以'#'结束：
";
initstack（optr）;
push（optr,'#'）;
initstack（opnd）;
cin.get（r）;
while（r!
='#'||gettop（optr）!
='#'）{
if（r>='0'&&r<='9'）
{
x=0;
while（r<='9'&&r>='0'）
{
x=x*10+r-'0';
cin.get（r）;
}
push（opnd,x）;
}
else
switch（precede（optr,r））
{
case-1:
push（optr,r）;
cin.get（r）;
break;
case0:
pop（optr,theta）;
cin.get（r）;
break;
case1:
s=pop（optr,theta）;
y=pop（opnd,b）;
z=pop（opnd,a）;
push（opnd,opterate（z,s,y））;
break;
}
}
cout<<"计算表达式的值为：
";
cout<}
四、运行测试（略）
升级会员 