昨天刚实现了栈的一些基本操作，今天就来实现一点栈的应用把！
首先，写一点比较简单的：
1.逆波兰表达式的计算。
在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。逆波兰表达式也称为后缀表达式。比如：
两种表达式如果在程序中运行时，后缀表达式不需要考虑符号优先级的问题。
现在通过一个程序去计算一个简单的后缀表达式：
计算
安全
数据库
网络和加速
企业服务
#pragma once
#include <iostream>
#include <assert.h>
#include <stack>
using namespace std;
enum Type
{
OP_NUM,//数字
OP_SYMBOL,//运算符
};
enum SYMBOL
{
ADD,
SUB,
MUL,
DIV,
};
struct Cell
{
Type _type;//类型（1.数字 2.运算符）
int _value;
};
int CountSymbol(Cell a[], size_t size)
{
assert(a);
stack<int> s;
for (size_t i = 0; i < size; i++)//依次读取每个数据
{
if (a[i]._type == OP_NUM)
{
s.push(a[i]._value);
}
else
{
//取出运算符前面的两个数字进行计算
int right = s.top();
s.pop();//栈的特性，只能pop一个后去下一个数
int left = s.top();
s.pop();
switch (a[i]._value)
{
//把计算结果压入栈中
case ADD:
s.push(left + right);
break;
case SUB:
s.push(left - right);
break;
case MUL:
s.push(left * right);
break;
case DIV:
s.push(left / right);
break;
}
}
}
return s.top();
}
void TestSymbol()
{
//12*(3+4)-6+8/2 = 82
//12 3 4 + * 6 - 8 2 / + 逆波兰表达式
Cell a[] =
{
{OP_NUM,12},
{OP_NUM, 3},
{OP_NUM,4},
{OP_SYMBOL,ADD},
{OP_SYMBOL,MUL},
{OP_NUM,6},
{OP_SYMBOL,SUB},
{OP_NUM,8},
{OP_NUM,2},
{OP_SYMBOL,DIV},
{OP_SYMBOL,ADD},
};
int ret = CountSymbol(a, sizeof(a) / sizeof(a[0]));
cout << "ret=" << ret << endl;
}
在这个程序中可以看到应用了栈的一个重要特性，“后进先出”。
2.迷宫是一个很长久的话题，今天我就用代码来实现它。
迷宫问题有一个很重要的点，就是“回溯”，顾名思义，就是沿着走过的路依次往回走。
为了简单起见，直接写一个迷宫，定义为“Maze.txt”文件
（0表示通路，1表示墙）
把走过的路的坐标保存在一个栈中，当无路可走的时候，从栈中依次pop出的坐标回溯，直到找到正确的路或者没有通路为止！
代码实现如下：
#pragma once
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#define N 10
#include <iostream>
#include <stack>
#include <assert.h>
using namespace std;
struct Pos//记录坐标
{
int _row;//行
int _col;//列
};
void GetMaze(int * a, int n)//读取迷宫
{
FILE * fout = fopen("Maze.txt", "r");
assert(fout);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; )
{
char ch = fgetc(fout);
if (ch == '0' || ch == '1')
{
a[i*n + j] = ch - '0';
j++;//有数据时，才往二维数组中存，所以j++放在这里
}
else
{
continue;
}
}
}
fclose(fout);
}
void printMaze(int * a, int n)//输出迷宫
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << a[i*n + j] << " ";
}
cout << endl;
}
}
bool CheckIsAccess(int * a, int n, Pos next)//检查是否通行
{
assert(a);
if (next._row >= 0 && next._row < n&&
next._col >= 0 && next._col < n&&
a[next._row*n + next._col] == 0)// 0 表示可以通行
{
return true;
}
else
{
return false;
}
}
bool MazePath(int *a, int n, const Pos & entry, stack<Pos>& path)
{
Pos cur = entry;
path.push(cur);
while (!path.empty())//栈空的时候返回起点
{
a[cur._row*n + cur._col] = 2;//走过的路标记为2
if (cur._row == n - 1)//判断是否到出口
{
return true;
}
//向上
Pos next = cur;
next._row--;
if (CheckIsAccess(a, n, next))//判断
{
cur = next;
path.push(cur);//走过的坐标push进栈
continue;
}
//向下
next = cur;//每次判断的时候重新赋值给next
next._row++;
if (CheckIsAccess(a, n, next))
{
cur = next;
path.push(cur);
continue;
}
//向左
next = cur;
next._col--;
if (CheckIsAccess(a, n, next))
{
cur = next;
path.push(cur);
continue;
}
//向右
next = cur;
next._col++;
if (CheckIsAccess(a, n, next))
{
cur = next;
path.push(cur);
continue;
}
//无路可走
a[cur._row*n + cur._col] = 3;
path.pop();
if (!path.empty())
{
cur = path.top();
}
}
return false;
}
void TestMaze()
{
int a[N][N] = {};
GetMaze((int *)a, N);
printMaze((int *)a, N);
stack<Pos> path;
Pos entry = { 2,0 };
MazePath((int *)a, N, entry, path);
cout << "结果" << endl;
printMaze((int *)a, N);
}输出的结果是：
数字“2”表示通路。
欢迎各位大神吐槽。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
