4. 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
输入样例
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
输出样例
[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
参考代码
#include <bits/stdc++.h> using namespace std; const int N = 110; int a[N][N]; int dist[N][N]; bool st[N][N]; const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; pair<int, int> pre[N][N]; int main() { int t; cin >> t; while (t--) { int n; cin >> n; memset(a, 0, sizeof a); memset(st, false, sizeof st); memset(dist, -1, sizeof dist); memset(pre, -1, sizeof pre); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cin >> a[i][j]; } if (a[n - 1][n - 1] == 1) { cout << "no path" << endl; continue; } queue<pair<int, int>> q; dist[n - 1][n - 1] = 0; pre[n - 1][n - 1] = {0, 0}; st[n - 1][n - 1] = 1; q.push({n - 1, n - 1}); while (q.size()) { pair<int, int> t = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = t.first + dx[i], y = t.second + dy[i]; if (x < 0 || x >= n || y < 0 || y >= n || st[x][y] || a[x][y] == 1) continue; if (pre[x][y].first != -1) continue; dist[x][y] = dist[t.first][t.second] + 1; q.push({x, y}); st[x][y] = 1; pre[x][y] = t; } } if (dist[0][0] == -1) { cout << "no path" << endl; } else { pair<int, int> end = make_pair(0, 0); int cnt = 0; while (true) { printf("[%d,%d]--", end.first, end.second); cnt++; if (cnt == 4) { cout << endl; cnt = 0; } if (end.first == n - 1 && end.second == n - 1) { break; } end = pre[end.first][end.second]; } cout << "END" << endl; } } return 0; }
5. DS堆栈–表达式计算
题目描述
计算一个表达式的运算结果
使用C++自带stack堆栈对象来实现
参考课本的算法伪代码P53-54
例如
Push (OPTR, ‘#’);表示把字符#压入堆栈OPTR中，转换成c++代码就是OPTR.push(’#’);
Pop(OPND, a); 表示弹出栈OPND的栈顶元素，并把栈顶元素放入变量a中。因此改成c++代码是两个操作：
a = OPND.top();
OPND.pop();
a = GetTop(OPND)表示获取栈OPND的栈顶元素，转成c++代码就是： a = OPND.top();
输入
第一个输入t，表示有t个实例
第二行起，每行输入一个表达式，每个表达式末尾带#表示结束
输入t行
输出
每行输出一个表达式的计算结果，计算结果用浮点数（含4位小数）的格式表示
用cout控制浮点数输出的小数位数，需要增加一个库文件，并使用fixed和setprecision函数，代码如下：
#include #include 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 <iomanip> #include <cstring> using namespace std; #define ok 0 #define error -1 #define overflow -1 #define opsetsize 7 typedef int Status; 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[opsetsize] = {'+', '-', '*', '/', '(', ')', '#'}; Status In(char Test, char *TestOp) { for (int i = 0; i < opsetsize; i++) { if (Test == TestOp[i]) return 1; } return ok; } char precede(char Aop, char Bop) { int i, j; for (i = 0; i < opsetsize; i++) { if (OPSET[i] == Aop) break; } for (j = 0; j < opsetsize; j++) { if (OPSET[j] == Bop) break; } return Prior[i][j]; } float EvaluateExpression(string MyExp) { stack<char> OPTR; stack<double> OPND; char TempData[20]; double Data, a, b, r; char theta, Dr[2]; char 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 '>': double a = OPND.top(); OPND.pop(); double b = OPND.top(); OPND.pop(); theta = OPTR.top(); OPTR.pop(); OPND.push(Operate(b, theta, a)); 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; }
