昨天刚实现了栈的一些基本操作，今天就来实现一点栈的应用把！
首先，写一点比较简单的：
1.逆波兰表达式的计算。
在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。逆波兰表达式也称为后缀表达式。比如：
两种表达式如果在程序中运行时，后缀表达式不需要考虑符号优先级的问题。
现在通过一个程序去计算一个简单的后缀表达式：
#pragma once #include#include #include 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 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#include #include 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 & 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 path; Pos entry = { 2,0 }; MazePath((int *)a, N, entry, path); cout << "结果" << endl; printMaze((int *)a, N); }
输出的结果是：
数字“2”表示通路。
欢迎各位大神吐槽。
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
