1 1实验项目二 栈的基本操作及其应用
截止时间：11月17日23:59 课程名称：数据结构 实验目的： 1．掌握栈的定义及实现； 2．掌握利用栈求解算术表达式的方法。 实验要求： 1、 使用链式存储结构完成栈的各种基本操作； 2、 补充完成In©, Preced(t1,t2),Operate(a,theta,b)三个函数。 实验题目：栈的基本操作及其应用 实验过程： 1、通过修改完善教材中的算法3.22，利用栈来实现算术表达式求值的算法。对算法3.22中调用的几个函数要给出其实现过程： (1) 函数In©：判断c是否为运算符； (2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级； (3) 函数Operate(a,theta,b)：对a和b进行二元运算theta。 2、程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号），便可输出相应的计算结果。 实验提示：（仅供参考，每个函数的具体实现可以有多种方法，希望有创新）
将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序中包含此头文件（即#include“stack.h”）。 2.表达式求值源程序的具体实现 (1) 主函数如下： void main() { Printf(“请输入算术表达式,并以#结束.\n”); Printf(“the result of expression is:%d\n”,EvaluateExpression()); } (2) 函数EvaluateExpression的实现见算法3.22 (3) 函数In©的实现可以采用以下方式： Status In(SElemType c)// 应在前面有定义typedef char SElemType; { // 判断c是否为运算符 switch© { case’+’:return TRUE; ……//补充完整 default:return FALSE; } } (4) 函数Precede(t1,t2)的实现可以采用以下形式： SElemType Precede(SElemType t1,SElemType t2) { //根据教材表3.1，判断两个运算符的优先关系 SElemType f; switch(t2) { case ‘+’: case ‘-’:if(t1==’(’||t1==’#’) f=’<’; else f=’>’; break; ……//补充完整 } return f; } (5) 函数Operate(a,theta,b)的实现可以采用以下方式： SElemType Operate(SElemType a,SElemType theta,SElemType b) { SElemType c; a=a-48; b=b-48; switch(theta) { case’+’:c=a+b+48; break; ……//补充完整 } return c; }
选做内容：进一步改进，使表达式的中间值及最终结果不局限于0～9之间的个位数。（如果完成要在实验报告中注明），如下图： 实验结果： 输入：2*（4-1）+8 输出：14 该程序能够完成个位数的四则运算。 实验分析： 1.栈的操作的特点； 2.列举调试运行过程中出现的错误并分析原因。 要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 上传源程序到课堂派，源程序保存为calculator.cpp。
1栈的实现
#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
using namespace std
;
#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll
;
struct Lnode
{
ll date
;
Lnode
*next
;
};
struct Sqlist
{
Lnode
*head
;
ll size
;
}List
;
void init()
{
List
.head
=NULL;
List
.size
=0;
return ;
}
bool
empty()
{
if(List
.size
==0)
return true
;
return false
;
}
void push(ll n
)
{
Lnode
*pos
=new Lnode
;
pos
->date
=n
;
if(List
.size
==0)
pos
->next
=NULL;
else
pos
->next
=List
.head
;
List
.head
=pos
;
List
.size
++;
return ;
}
ll
top()
{
if(empty())
{
cout
<<"栈已空,执行空操作"<<endl
;
return -1;
}
return List
.head
->date
;
}
void pop()
{
if(empty())
{
cout
<<"栈已空,执行空操作"<<endl
;
return ;
}
Lnode
*pos
=List
.head
;
List
.head
=pos
->next
;
delete pos
;
List
.size
--;
return ;
}
ll
size()
{
return List
.size
;
}
int main()
{
ll i
,j
;
ll N
;
while(cin
>>N
)
{
init();
for(i
=0;i
<N
;i
++)
{
ll n
;
cin
>>n
;
push(n
);
}
while(!empty())
{
ll n
=top();
pop();
cout
<<n
<<' ';
}
cout
<<endl
;
}
return 0;
}
1用栈实现基本的算术运算
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std
;
#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll
;
const ll maxn
=300;
string S
,s
;
string suffix
[maxn
],infix
[maxn
];
ll sulen
,inlen
;
ll
Tran(string s
)
{
ll sum
=0,i
,j
;
for(i
=0;i
<s
.length();i
++)
sum
=sum
*10+s
[i
]-'0';
return sum
;
}
void Suffix_Infix()
{
ll i
,j
;
stack
<string
>sta
;
inlen
=0;
for(i
=0;i
<sulen
-1;i
++)
{
if(suffix
[i
].length()==1)
{
if(suffix
[i
][0]=='+'||suffix
[i
][0]=='-')
{
while(!sta
.empty())
{
string jie
=sta
.top();
if(jie
[0]=='(')
break;
infix
[inlen
++]=jie
;
sta
.pop();
}
sta
.push(suffix
[i
]);
}
else if(suffix
[i
][0]=='*'||suffix
[i
][0]=='/')
{
while(!sta
.empty())
{
string jie
=sta
.top();
if(jie
[0]=='('||jie
[0]=='+'||jie
[0]=='-')
break;
infix
[inlen
++]=jie
;
sta
.pop();
}
sta
.push(suffix
[i
]);
}
else if(suffix
[i
][0]=='(')
sta
.push(suffix
[i
]);
else if(suffix
[i
][0]==')')
{
while(!sta
.empty())
{
string jie
=sta
.top();
if(jie
[0]=='(')
{
sta
.pop();
break;
}
infix
[inlen
++]=jie
;
sta
.pop();
}
}
else
infix
[inlen
++]=suffix
[i
];
}
else
infix
[inlen
++]=suffix
[i
];
}
while(!sta
.empty())
{
infix
[inlen
++]=sta
.top();
sta
.pop();
}
return ;
}
double Eva(string
*infix
)
{
stack
<double>Jie
;
ll i
,j
;
for(i
=0;i
<inlen
;i
++)
{
if(infix
[i
][0]>='1'&&infix
[i
][0]<='9')
{
double sum
=double(Tran(infix
[i
]));
Jie
.push(sum
);
}
else
{
double sum
=Jie
.top();
Jie
.pop();
double Sum
=Jie
.top();
Jie
.pop();
if(infix
[i
][0]=='+')
Sum
+=sum
;
else if(infix
[i
][0]=='-')
Sum
-=sum
;
else if(infix
[i
][0]=='*')
Sum
*=sum
;
else if(infix
[i
][0]=='/')
Sum
/=sum
;
Jie
.push(Sum
);
}
}
double sum
=Jie
.top();
Jie
.pop();
return sum
;
}
int main()
{
ios
::sync_with_stdio(false
);
cout
<<"请输入表达式:(支持加减乘除括号多位数操作)"<<endl
;
while(cin
>>S
)
{
ll i
,j
;
s
="";
for(i
=0;i
<S
.length();i
++)
{
if(S
[i
]=='+'||S
[i
]=='-'||S
[i
]=='*'||S
[i
]=='/'||S
[i
]=='('||S
[i
]==')')
{
s
+=' ';
s
+=S
[i
];
s
+=' ';
}
else
s
+=S
[i
];
}
sulen
=0;
stringstream
ss(s
);
while(ss
>>suffix
[sulen
++]);
Suffix_Infix();
cout
<<"输出结果:"<<endl
;
cout
<<Eva(infix
)<<endl
;
}
return 0;
}
