DS|堆栈

题目一：DS堆栈--逆序输出（STL栈使用）

题目描述：

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

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

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

输入要求：

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

输出要求：

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

输入样例：

2
abcdef
aabbcc

输出样例：

fedcba
ccbbaa

代码示例：

#include <iostream>
#include<vector>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		string str;
		cin >> str;
		int len = str.length();
		vector<char> s;
		for (int i = len - 1; i >= 0; i--) s.push_back(str[i]);
		for (int i = 0; i < len; i++) cout << s[i];
		cout << endl;
	}
}

题目二：DS堆栈--行编辑

题目描述：

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

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

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

输入要求：

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

输出要求：

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

输入样例：

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

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

输出样例：

china
szu
sz
NULL

NULL

代码示例：

#include <iostream>
#include<vector>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		string str;
		cin >> str;
		vector<char> a;

		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '#' && a.size() != 0) a.pop_back();
			else if (str[i] != '#') a.push_back(str[i]);
		}
		if (a.size()) {
			for (int i = 0; i < a.size(); i++) cout << a[i];
			cout << endl;
		}
		else cout << "NULL" << endl;
	}
}

题目三：DS堆栈--迷宫求解

题目描述：

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

输入要求：

第一行输入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

输入样例：

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

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

输出样例：

[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

[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

代码示例：

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

// 定义结构表示网格中的索引 (x, y)
struct index
{
    int x, y;
};

int main() {
    int t;
    cin >> t; // 测试用例的数量
    while (t--)
    {
        stack<index> path; // 用于存储路径的栈
        int n;
        cin >> n; // 网格的大小 (n x n)

        // 动态分配内存以表示网格的二维数组
        int** array = new int* [n];
        for (int i = 0; i < n; i++) {
            array[i] = new int[n];
            for (int j = 0; j < n; j++) 
                cin >> array[i][j]; // 输入网格元素
        }

        path.push({0, 0}); // 起点
        array[0][0] = 1; // 标记起点为已访问

        int i = 0, j = 0; // 当前位置在网格中的坐标
        while (1){
            // 尝试向右移动
            if (j + 1 < n && array[i][j + 1] == 0){
                array[i][j + 1] = 1; // 标记该位置为已访问
                path.push({i, ++j}); // 更新当前位置
            }
            // 尝试向下移动
            else if (i + 1 < n && array[i + 1][j] == 0){
                array[i + 1][j] = 1;
                path.push({++i, j});
            }
            // 尝试向左移动
            else if (j - 1 >= 0 && array[i][j - 1] == 0){
                array[i][j - 1] = 1;
                path.push({i, --j});
            }
            // 尝试向上移动
            else if (i - 1 >= 0 && array[i - 1][j] == 0){
                array[i - 1][j] = 1;
                path.push({--i, j});
            }
            else {
                // 如果没有有效移动，则回溯
                path.pop();
                if (!path.empty()){
                    i = path.top().x;
                    j = path.top().y;
                }
            }
            
            // 检查终止条件
            if (path.empty() || (i == n - 1 && j == n - 1))
                break;
        }
        
        // 输出结果
        if (path.empty())
            cout << "no path" << endl;
        else {
            stack<index> path1;
            // 将路径逆序以正确的顺序打印
            while (!path.empty()) {
                path1.push(path.top());
                path.pop();
            }
            i = 0;
            while (!path1.empty()) {
                // 每4步打印在新行上
                if ((++i) % 4 == 0) 
                    cout << '[' << path1.top().x << ',' << path1.top().y << ']' << "--" << endl;
                else 
                    cout << '[' << path1.top().x << ',' << path1.top().y << ']' << "--";
                path1.pop();
            }
            cout << "END" << endl;
        }
        
        // 释放网格内存
        for (int i = 0; i < n; i++) {
            delete[] array[i];
        }
        delete[] array;
    }
    return 0;
}

问题四：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、 若到最后，括号不能完全匹配，则说明输入的表达式有错

输入要求：

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

输出要求：

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

输入样例：

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

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

输出样例：

ok
error

ok
ok
ok
ok

代码示例：

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
using namespace std;

bool match(char ch1, char ch2) {
	if (ch1 == '(' && ch2 == ')') return true;
	else if (ch1 == '[' && ch2 == ']') return true;
	else if (ch1 == '{' && ch2 == '}') return true;
	else return false;
}

int main() {
	int t;
	cin >> t;
	while (t--){
		string str;
		cin >> str;
		vector<char> s;
		int count = 0;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '(' || str[i] == ')' || str[i] == '[' || str[i] == ']' || str[i] == '{' || str[i] == '}') {
				s.push_back(str[i]);
				count++;
			}
			if (count >= 2 && match(s[count - 2], s[count - 1])) {
				count -= 2;
				s.pop_back(), s.pop_back();
			}
		}
		if (s.empty()) cout << "ok" << endl;
		else cout << "error" << endl;
	}
	return 0;
}

问题五：DS堆栈--表达式计算

题目描述：

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

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

输入要求：

第一个输入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

输入样例：

2
1+2*3-4/5#
(66+(((11+22)*2-33)/3+6)*2)-45.6789#

输出样例：

6.2000
54.3211

代码示例：

#include<iostream>
#include<stack>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iomanip>

using namespace std;

char prior[7][7] = {	//算符间的优先关系
	'>','>','<','<','<','>','>',
	'>','>','<','<','<','>','>',
	'>','>','>','>','<','>','>',
	'>','>','>','>','<','>','>',
	'<','<','<','<','<','=',' ',
	'>','>','>','>',' ','>','>',
	'<','<','<','<','<',' ','='
};

float operate(float a, unsigned char theta, float b){
	if (theta == '+') return a + b;
	else if (theta == '-') return a - b;
	else if (theta == '*') return a * b;
	else if (theta == '/') return a / b;
}

char opset[7] = { '+','-','*','/','(',')','#' };//运算符集合

bool In(char Test, char* TestOp){
	for (int i = 0; i < 7; i++) if (Test == TestOp[i]) return true;
	return false;
}

char precede(char Aop, char Bop){
	int i, j;
	for (i = 0; i < 7; i++) if (opset[i] == Aop) break;
	for (j = 0; j < 7; j++) if (opset[j] == Bop) break;
	return prior[i][j];
}

float Evaluate(string MyExp){
	stack<char> OPTR;
	stack<double> OPND;
	char TempData[20];
	double Data, a, b, r;
	char theta, Dr[2], c;
	int i = 0;

	OPTR.push('#');
	c = MyExp[0];

	strcpy(TempData, "\0");
	while (c != '#' || OPTR.top() != '#'){
		if (!In(c, opset)){
			Dr[0] = c;
			Dr[1] = '\0';
			strcat(TempData, Dr);
			c = MyExp[++i];
			if (In(c, opset)){
				Data = (float)atof(TempData);
				OPND.push(Data);
				strcpy(TempData, "\0");
			}
		}
		else{
			switch (precede(OPTR.top(), c)){
			case '<':
				OPTR.push(c);
				c = MyExp[++i];
				break;
			case '=':
				OPTR.pop();
				c = MyExp[++i];
				break;
			case '>':
				theta = OPTR.top(); OPTR.pop();
				b = OPND.top(); OPND.pop();
				a = 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 = Evaluate(Exp);
		cout << fixed << setprecision(4) << result << endl;
	}
	return 0;
}