棧的一些小小應(yīng)用
昨天剛實(shí)現(xiàn)了棧的一些基本操作，今天就來實(shí)現(xiàn)一點(diǎn)棧的應(yīng)用把！
在鐘祥等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì) 網(wǎng)站設(shè)計(jì)制作定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,營(yíng)銷型網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè)公司,鐘祥網(wǎng)站建設(shè)費(fèi)用合理。
首先，寫一點(diǎn)比較簡(jiǎn)單的：
1.逆波蘭表達(dá)式的計(jì)算。
在通常的表達(dá)式中，二元運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，這種表示法也稱為中綴表示。逆波蘭表達(dá)式也稱為后綴表達(dá)式。比如：
兩種表達(dá)式如果在程序中運(yùn)行時(shí)，后綴表達(dá)式不需要考慮符號(hào)優(yōu)先級(jí)的問題。
現(xiàn)在通過一個(gè)程序去計(jì)算一個(gè)簡(jiǎn)單的后綴表達(dá)式：
#pragma once #include#include #include using namespace std; enum Type { OP_NUM,//數(shù)字 OP_SYMBOL,//運(yùn)算符 }; enum SYMBOL { ADD, SUB, MUL, DIV, }; struct Cell { Type _type;//類型（1.數(shù)字 2.運(yùn)算符） int _value; }; int CountSymbol(Cell a[], size_t size) { assert(a); stack s; for (size_t i = 0; i < size; i++)//依次讀取每個(gè)數(shù)據(jù) { if (a[i]._type == OP_NUM) { s.push(a[i]._value); } else { //取出運(yùn)算符前面的兩個(gè)數(shù)字進(jìn)行計(jì)算 int right = s.top(); s.pop();//棧的特性，只能pop一個(gè)后去下一個(gè)數(shù) int left = s.top(); s.pop(); switch (a[i]._value) { //把計(jì)算結(jié)果壓入棧中 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 / + 逆波蘭表達(dá)式 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; }
在這個(gè)程序中可以看到應(yīng)用了棧的一個(gè)重要特性，“后進(jìn)先出”。
2.迷宮是一個(gè)很長(zhǎng)久的話題，今天我就用代碼來實(shí)現(xiàn)它。
迷宮問題有一個(gè)很重要的點(diǎn)，就是“回溯”，顧名思義，就是沿著走過的路依次往回走。
為了簡(jiǎn)單起見，直接寫一個(gè)迷宮，定義為“Maze.txt”文件
（0表示通路，1表示墻）
把走過的路的坐標(biāo)保存在一個(gè)棧中，當(dāng)無(wú)路可走的時(shí)候，從棧中依次pop出的坐標(biāo)回溯，直到找到正確的路或者沒有通路為止！
代碼實(shí)現(xiàn)如下：
#pragma once #pragma once #define _CRT_SECURE_NO_WARNINGS 1 #define N 10 #include#include #include using namespace std; struct Pos//記錄坐標(biāo) { 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++;//有數(shù)據(jù)時(shí)，才往二維數(shù)組中存，所以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())//?？盏臅r(shí)候返回起點(diǎn) { a[cur._row*n + cur._col] = 2;//走過的路標(biāo)記為2 if (cur._row == n - 1)//判斷是否到出口 { return true; } //向上 Pos next = cur; next._row--; if (CheckIsAccess(a, n, next))//判斷 { cur = next; path.push(cur);//走過的坐標(biāo)push進(jìn)棧 continue; } //向下 next = cur;//每次判斷的時(shí)候重新賦值給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; } //無(wú)路可走 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 << "結(jié)果" << endl; printMaze((int *)a, N); }
輸出的結(jié)果是：
數(shù)字“2”表示通路。
歡迎各位大神吐槽。
本文標(biāo)題：棧的一些小小應(yīng)用
本文鏈接：http://www.jiaotiyi.com/article/jcdeeh.html