大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
昨天刚实现了栈的一些基本操作,今天就来实现一点栈的应用把!
在钟祥等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站建设、成都网站设计 网站设计制作定制开发,公司网站建设,企业网站建设,品牌网站制作,营销型网站建设,成都外贸网站建设公司,钟祥网站建设费用合理。
首先,写一点比较简单的:
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”表示通路。
欢迎各位大神吐槽。