昨天刚实现了栈的一些基本操作，今天就来实现一点栈的应用把！

首先，写一点比较简单的：

1.逆波兰表达式的计算。

在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。逆波兰表达式也称为后缀表达式。比如：

两种表达式如果在程序中运行时，后缀表达式不需要考虑符号优先级的问题。

现在通过一个程序去计算一个简单的后缀表达式：

#pragmaonce#include<iostream>#include<assert.h>#include<stack>usingnamespacestd;enumType{OP_NUM,//数字OP_SYMBOL,//运算符};enumSYMBOL{ADD,SUB,MUL,DIV,};structCell{Type_type;//类型（1.数字2.运算符）int_value;};intCountSymbol(Cella[],size_tsize){assert(a);stack<int>s;for(size_ti=0;i<size;i++)//依次读取每个数据{if(a[i]._type==OP_NUM){s.push(a[i]._value);}else{//取出运算符前面的两个数字进行计算intright=s.top();s.pop();//栈的特性，只能pop一个后去下一个数intleft=s.top();s.pop();switch(a[i]._value){//把计算结果压入栈中caseADD:s.push(left+right);break;caseSUB:s.push(left-right);break;caseMUL:s.push(left*right);break;caseDIV:s.push(left/right);break;}}}returns.top();}voidTestSymbol(){//12*(3+4)-6+8/2=82//1234+*6-82/+逆波兰表达式Cella[]={{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},};intret=CountSymbol(a,sizeof(a)/sizeof(a[0]));cout<<"ret="<<ret<<endl;}

在这个程序中可以看到应用了栈的一个重要特性，“后进先出”。

2.迷宫是一个很长久的话题，今天我就用代码来实现它。

迷宫问题有一个很重要的点，就是“回溯”，顾名思义，就是沿着走过的路依次往回走。

为了简单起见，直接写一个迷宫，定义为“Maze.txt”文件

（0表示通路，1表示墙）

把走过的路的坐标保存在一个栈中，当无路可走的时候，从栈中依次pop出的坐标回溯，直到找到正确的路或者没有通路为止！

代码实现如下：

#pragmaonce#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#defineN10#include<iostream>#include<stack>#include<assert.h>usingnamespacestd;structPos//记录坐标{int_row;//行int_col;//列};voidGetMaze(int*a,intn)//读取迷宫{FILE*fout=fopen("Maze.txt","r");assert(fout);for(inti=0;i<n;i++){for(intj=0;j<n;){charch=fgetc(fout);if(ch=='0'||ch=='1'){a[i*n+j]=ch-'0';j++;//有数据时，才往二维数组中存，所以j++放在这里}else{continue;}}}fclose(fout);}voidprintMaze(int*a,intn)//输出迷宫{for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i*n+j]<<"";}cout<<endl;}}boolCheckIsAccess(int*a,intn,Posnext)//检查是否通行{assert(a);if(next._row>=0&&next._row<n&&next._col>=0&&next._col<n&&a[next._row*n+next._col]==0)//0表示可以通行{returntrue;}else{returnfalse;}}boolMazePath(int*a,intn,constPos&entry,stack<Pos>&path){Poscur=entry;path.push(cur);while(!path.empty())//栈空的时候返回起点{a[cur._row*n+cur._col]=2;//走过的路标记为2if(cur._row==n-1)//判断是否到出口{returntrue;}//向上Posnext=cur;next._row--;if(CheckIsAccess(a,n,next))//判断{cur=next;path.push(cur);//走过的坐标push进栈continue;}//向下next=cur;//每次判断的时候重新赋值给nextnext._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();}}returnfalse;}voidTestMaze(){inta[N][N]={};GetMaze((int*)a,N);printMaze((int*)a,N);stack<Pos>path;Posentry={2,0};MazePath((int*)a,N,entry,path);cout<<"结果"<<endl;printMaze((int*)a,N);}

输出的结果是：

数字“2”表示通路。

欢迎各位大神吐槽。