STL之栈(链表实现)
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<bits/stdc++.h>
#include<cstdio>
//#include<cstring>
#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;//head指向第一个元素
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()
{
// freopen(".../.txt","w",stdout);
// ios::sync_with_stdio(false);
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中
{
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()
{
// freopen(".../.txt","w",stdout);
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;
}
拼多多集团-PDD成长空间 486人发布