数据结构OJ实验3-堆栈

发布时间:2024年01月02日

A. DS堆栈--逆序输出(STL栈使用)

题目描述

C++中已经自带堆栈对象stack,无需编写堆栈操作的具体实现代码。

本题目主要帮助大家熟悉stack对象的使用,然后实现字符串的逆序输出

输入一个字符串,按字符按输入顺序压入堆栈,然后根据堆栈后进先出的特点,做逆序输出

stack类使用的参考代码

n包含头文件<stack>:#include <stack>

n创建一个堆栈对象s(注意stack是模板类):stack <char> ?s;//堆栈的数据类型是字符型

n把一个字符ct压入堆栈:s.push(ct);

n把栈顶元素弹出:s.pop();

n获取栈顶元素,放入变量c2:c2 =s.top();

n判断堆栈是否空:s.empty(),如果为空则函数返回true,如果不空则返回false

输入

第一行输入t,表示有t个测试实例
第二起,每一行输入一个字符串,注意字符串不要包含空格

字符串的输入可以考虑一下代码:

#include <string>

int main()

{ string str;

Int len;

cin>>str; //把输入的字符串保存在变量str中

len = str.length()? //获取输入字符串的长度

}

输出

每行逆序输出每一个字符串

样例查看模式?

正常显示查看格式

输入样例1?

2
abcdef
aabbcc

输出样例1

fedcba
ccbbaa

AC代码

#include<iostream>
#include<stack>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		stack<char>st;
		for (int i = 0; i < s.size(); i++)
		{
			st.push(s[i]);
		}
		while(!st.empty())
		{
			cout << st.top();
			st.pop();
		}
		cout << endl;
	}
	return 0;
}

B. DS堆栈--行编辑

题目描述

使用C++的STL堆栈对象,编写程序实现行编辑功能。行编辑功能是:当输入#字符,则执行退格操作;如果无字符可退就不操作,不会报错

本程序默认不会显示#字符,所以连续输入多个#表示连续执行多次退格操作

每输入一行字符打回车则表示字符串结束

注意:必须使用堆栈实现,而且结果必须是正序输出

输入

第一行输入一个整数t,表示有t行字符串要输入
第二行起输入一行字符串,共输入t行

输出

每行输出最终处理后的结果,如果一行输入的字符串经过处理后没有字符输出,则直接输出NULL

样例查看模式?

正常显示查看格式

输入样例1

4
chinaa#
sb#zb#u
##shen###zhen###
chi##a#####

输出样例1

china
szu
sz
NULL

输入样例2?

1
###############################################################################################

输出样例2

NULL

AC代码

#include<iostream>
#include<stack>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		stack<char>st;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] != '#')st.push(s[i]);
			else
			{
				if (!st.empty())
				{
					st.pop();
				}
			}
		}
		stack<char>ans;
		while(!st.empty())
		{
			ans.push( st.top());
			st.pop();
		}
		if (ans.empty())
		{
			cout << "NULL" << endl;
		}
		else
		{
			while (!ans.empty())
			{
				cout << ans.top();
				ans.pop();
			}
			cout << endl;
		}
	}
	return 0;
}

C. DS堆栈--迷宫求解

题目描述

给出一个N*N的迷宫矩阵示意图,从起点[0,0]出发,寻找路径到达终点[N-1, N-1]

要求使用堆栈对象来实现,具体算法参考课本3.2.4节51页

输入

第一行输入t,表示有t个迷宫

第二行输入n,表示第一个迷宫有n行n列

第三行起,输入迷宫每一行的每个方格的状态,0表示可通过,1表示不可通过

输入n行

以此类推输入下一个迷宫

输出

逐个输出迷宫的路径

如果迷宫不存在路径,则输出no path并回车

如果迷宫存在路径,将路径中每个方格的x和y坐标输出,从起点到终点,每输出四个方格就换行,最终以单词END结尾,具体格式参考示范数据

输出的代码参考如下:

//path是保存路径的堆栈,堆栈中每个元素都包含x坐标和y坐标,用属性xp和yp表示

//path1是一个临时堆栈,把path的数据倒序输出到path1,使得路径按正序输出

if (!path.empty())//找到路径

{//......若干代码,实现path的数据导入path1

i=0; ?//以下是输出路径的代码

while (!path1.empty())

{cpos = path1.top();

if ( (++i)%4 == 0 )

cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--"<<endl;

else

cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--";

path1.pop();

}

cout<<"END"<<endl;

}

else

cout<<"no path"<<endl; //找不到路径输出no path

样例查看模式?

正常显示查看格式

输入样例1?

2
8
0?0?0?1?1?1?1?1
1?0?0?0?1?0?0?1
1?0?0?0?1?0?0?0
1?1?0?0?0?0?0?1
0?0?1?1?0?1?1?0
0?0?0?0?0?0?1?1
1?1?1?1?1?0?0?1
0?0?0?0?1?0?0?0
7
0?0?0?1?1?1?1
1?0?0?1?0?0?1
1?0?0?1?0?0?0
1?1?0?0?0?0?1
0?0?1?1?0?1?0
1?0?0?0?0?1?0
0?0?0?0?1?1?0

输出样例1

[0,0]--[0,1]--[0,2]--[1,2]--
[1,3]--[2,3]--[3,3]--[3,4]--
[4,4]--[5,4]--[5,5]--[6,5]--
[6,6]--[7,6]--[7,7]--END
no?path

输入样例2?

2
12
0?1?1?1?1?1?1?1?1?1?1?0
0?0?0?0?0?0?0?0?0?0?0?1
0?1?1?1?1?0?1?1?1?1?0?1
1?0?0?0?0?0?0?0?0?0?0?1
0?0?1?1?1?1?0?1?0?1?1?0
0?1?1?1?1?1?1?1?1?1?0?0
0?0?0?0?0?0?0?0?0?0?0?1
1?1?1?1?0?1?1?1?1?1?0?1
1?1?1?1?1?0?1?1?1?1?0?1
1?1?1?1?1?0?0?0?0?0?0?0
1?1?1?1?1?1?1?1?0?1?1?1
0?1?0?1?0?1?0?1?0?0?0?0
12
0?1?1?1?1?1?1?1?1?1?1?0
0?0?0?0?0?0?0?0?0?0?0?1
0?1?1?1?1?0?1?1?1?1?0?1
1?0?0?0?0?0?0?0?0?0?0?1
0?0?1?1?1?1?0?1?0?1?1?0
0?1?1?1?1?1?1?1?1?1?0?0
0?0?0?0?0?0?0?0?0?0?1?1
1?1?1?1?0?1?1?1?1?1?0?1
1?1?1?1?1?0?1?1?1?1?0?1
1?1?1?1?1?0?0?0?0?0?0?0
1?1?1?1?1?1?1?1?0?1?1?1
0?1?0?1?0?1?0?1?0?0?0?0

输出样例2

[0,0]--[1,0]--[1,1]--[1,2]--
[1,3]--[1,4]--[1,5]--[1,6]--
[1,7]--[1,8]--[1,9]--[1,10]--
[2,10]--[3,10]--[3,9]--[3,8]--
[3,7]--[3,6]--[3,5]--[3,4]--
[3,3]--[3,2]--[3,1]--[4,1]--
[4,0]--[5,0]--[6,0]--[6,1]--
[6,2]--[6,3]--[6,4]--[6,5]--
[6,6]--[6,7]--[6,8]--[6,9]--
[6,10]--[7,10]--[8,10]--[9,10]--
[9,9]--[9,8]--[10,8]--[11,8]--
[11,9]--[11,10]--[11,11]--END
no?path

AC代码

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
void GoMaze(int n)
{
	//vector开二维数组
	vector<vector<int>>g(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin>> g[i][j];
		}
	}
	//起点和终点不通
	if (g[0][0] == 1 || g[n - 1][n - 1] == 1)
	{
		cout << "no path" << endl;
		return;
	}
	stack<pair<int, int>>path;
	int x = 0, y = 0;
	bool flag = 0;
	path.push({ x,y });
	while (!path.empty())
	{
		g[x][y] = 1;//走过不再走
		if (y + 1 <= n - 1 && g[x][y + 1] == 0)//先向下
		{
			y++;
			path.push({ x,y });
		}
		else if (x + 1 <= n - 1 && g[x + 1][y] == 0)//再向右
		{
			x++;
			path.push({ x,y });
		}
		else if (y - 1 >= 0 && g[x][y - 1] == 0)//向上退回
		{
			y--;
			path.push({ x,y });
		}
		else if (x - 1 >= 0 && g[x - 1][y] == 0)//向左退回
		{
			x--;
			path.push({ x,y });
		}
		else
		{
			//不能前进也无法退回(例如)
			//---1
			//11-1
			//1111
			//退回原来的位置,再次选择
			path.pop();//此位置不行
			if (!path.empty())//每次pop前都要判断,预防报错
			{
				auto tt = path.top();//使用栈体现,刚刚走过的
				x = tt.first;
				y = tt.second;
			}
		}
		if (x == n - 1 && y == n - 1)
		{
			flag = 1;
			break;
		}
	}
	if (flag)
	{
		stack<pair<int, int>>temp;
		while (!path.empty())
		{
			temp.push(path.top());
			path.pop();
		}
		int count = 0;
		while (!temp.empty())
		{
			cout << "[" << temp.top().first << "," << temp.top().second << "]";
			count++;
			temp.pop();
			cout << "--";
			if (count == 4)
			{
				count = 0;
				cout << endl;
			}
		}
		cout << "END" << endl;
	}
	else
	{
		cout << "no path" << endl;
	}
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		GoMaze(n);
	}
	return 0;
}

D. DS堆栈--括号匹配

题目描述

处理表达式过程中需要对括号匹配进行检验,括号匹配包括三种:“(”和“)”,“[”和“]”,“{”和“}”。例如表达式中包含括号如下:

(	)	[	(	)	(	[	]	)	]	{	}
1	2	3	4	5	6	7	8	9	10	11	12

从上例可以看出第1和第2个括号匹配,第3和第10个括号匹配,4和5匹配,6和9匹配,7和8匹配,11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的,使用堆栈可以很方便的处理这种括号匹配检验,可以遵循以下规则:

1、 当接收第1个左括号,表示新的一组匹配检查开始;随后如果连续接收到左括号,则不断进堆栈。

2、 当接受第1个右括号,则和最新进栈的左括号进行匹配,表示嵌套中1组括号已经匹配消除

3、 若到最后,括号不能完全匹配,则说明输入的表达式有错

建议使用C++自带的stack对象来实现

stack类使用的参考代码

n包含头文件<stack>:#include <stack>

n创建一个堆栈对象s(注意stack是模板类):stack <char> ?s;//堆栈的数据类型是字符型

n把一个字符ct压入堆栈:s.push(ct);

n把栈顶元素弹出:s.pop();

n获取栈顶元素,放入变量c2:c2 =s.top();

n判断堆栈是否空:s.empty(),如果为空则函数返回true,如果不空则返回false

输入

第一行输入一个t,表示下面将有t组测试数据。接下来的t行的每行输入一个表达式,表达式只考虑英文半角状态输入,无需考虑中文全角输入

输出

对于每一行的表达式,检查括号是否匹配,匹配则输入ok,不匹配则输出error

样例查看模式?

正常显示查看格式

输入样例1?

2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6

输出样例1

ok
error

输入样例2?

4
{1+1}[3+3](5+5)
((({{{}}})))
((({{{}}})))([[]])
((({{{5+5}}})))([[]])(1+1)

输出样例2

ok
ok
ok
ok

AC代码

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		stack<char>st;
		bool flag = 0;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '(' || s[i] == '[' || s[i] == '{')
			{
				st.push(s[i]);
			}
			else if (s[i] == ')')
			{
				if (st.top() != '(')
				{
					flag = 1;
					break;
				}
				else
				{
					st.pop();
				}
			}
			else if (s[i] == ']')
			{
				if (st.top() != '[')
				{
					flag = 1;
					break;
				}
				else
				{
					st.pop();
				}
			}
			else if (s[i] == '}')
			{
				if (st.top() != '{')
				{
					flag = 1;
					break;
				}
				else
				{
					st.pop();
				}
			}
			else continue;
		}
		if (flag || !st.empty())
		{
			cout << "error" << endl;
		}
		else cout << "ok" << endl;
	}
	return 0;
}

E. DS堆栈--表达式计算

题目描述

计算一个表达式的运算结果

使用C++自带stack堆栈对象来实现

参考课本的算法伪代码P53-54

例如

1. Push (OPTR, '#');表示把字符#压入堆栈OPTR中,转换成c++代码就是OPTR.push('#');

2. Pop(OPND, a); 表示弹出栈OPND的栈顶元素,并把栈顶元素放入变量a中。因此改成c++代码是两个操作:

a = OPND.top(); ? OPND.pop();

3. a = GetTop(OPND)表示获取栈OPND的栈顶元素,转成c++代码就是: a = OPND.top()

输入

第一个输入t,表示有t个实例

第二行起,每行输入一个表达式,每个表达式末尾带#表示结束

输入t行

输出

每行输出一个表达式的计算结果,计算结果用浮点数(含4位小数)的格式表示

用cout控制浮点数输出的小数位数,需要增加一个库文件,并使用fixed和setprecision函数,代码如下:

#include <iostream>
#include<iomanip>
using namespace std;

int main()

{ double temp = 12.34

cout<<fixed<<setprecision(4)<<temp<<endl;

}

输出结果为12.3400

AC代码

#include<bits/stdc++.h>
using namespace std;
char opset[7]={'+','-','*','/','(',')','#'};
char Prior[7][7]=//列为当前,行为栈顶
{
    '>','>','<','<','<','>','>',
    '>','>','<','<','<','>','>',
    '>','>','>','>','<','>','>',
    '>','>','>','>','<','>','>',
    '<','<','<','<','<','=',' ',
    '>','>','>','>',' ','>','>',
    '<','<','<','<','<',' ','='
};
char precede(char aop,char bop)
{
    int x,y;
    for(int i=0;i<7;i++)
    {
        if(opset[i]==aop)
        {
            x=i;
        }
        if(opset[i]==bop)
        {
            y=i;
        }
    }
    return Prior[x][y];
}
int In(char Test,char* Testop)
{
    for(int i=0;i<7;i++)
    {
        if(Test==Testop[i])
        {
            return 1;
        }
    }
    return 0;
}
double Operate(double a,char theta,double b)
{
    if(theta=='+')
    {
        return a+b;
    }
    else if(theta=='-')
    {
        return b-a;
    }
    else if(theta=='*')
    {
        return a*b;
    }
    else if(theta=='/')
    { 
        return b/a;
    }
    //-----a/b  stack(b/a)
}
double EvaluateExpression(string exp)
{
    stack<double>opnd;//操作数
    stack<char>optr;//操作运算符
    char tempdata[20];
    double data,a,b,r;
    char theta,dr[2];
    char c;
    int i=0;
    //先放入#
    optr.push('#');
    c=exp[0];
    strcpy(tempdata,"\0");
    //遇到两个#停止
    while(c!='#'||optr.top()!='#')
    {
        if(!In(c,opset))//不是运算符,是数字
        {
            dr[0]=c;
            dr[1]='\0';
            strcat(tempdata,dr);
            //c为下一个字符
            c=exp[++i];
            //c是运算符
            if(In(c,opset))
            {
                //转换为数字
               data=(double)atof(tempdata);
               opnd.push(data);
               strcpy(tempdata,"\0");
            }
        }
        else//是数字
        {
            switch(precede(optr.top(),c))
            {
                case '<'://栈顶元素优先权低
                optr.push(c);
                c=exp[++i];
                break;
                case '=':
                optr.pop();
                c=exp[++i];
                break;
                case '>'://栈顶元素优先权低
                theta=optr.top();
                optr.pop();
                a=opnd.top();
                opnd.pop();
                b=opnd.top();
                opnd.pop();
                opnd.push(Operate(a,theta,b));
                break;
            }
        }
    }
    return opnd.top();
}
int main()
{
    string exp;
    int t;
    double result;
    cin>>t;
    while(t--)
    {
        cin>>exp;
        result=EvaluateExpression(exp);
        cout<<fixed<<setprecision(4)<<result<<endl;
    }
    return 0;
}

文章来源:https://blog.csdn.net/gyeolhada/article/details/135322224
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。