• 基本知识

//声明使用标准命名空间
#include <stack>//定义一个保存元素类型为int的堆栈S
stack<int> S;//加入一个元素i
S.push(i);//删一个元素
S.pop();//读栈顶元素，给x
int x=S.top();//判断栈是否空,空返回true,非空返回false
S.empty();//栈中的元素个数
int a=S.size();

• 例题1、括号匹配

寻找不匹配的左右括号，（不匹配下面标$ ； ）不匹配下面标？

思路：从左到右遍历字符串，遇到(入栈；遇到)若栈不空出栈一个，若栈空匹配错误。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<stack>
using namespace std;stack<int> S;
char str[110];//保存输入字符
char ans[110];//保存输出字符int main()
{while(cin>>str){int len=strlen(str),i;for(i=0;i<len;i++)//遍历字符串{if(str[i]=='(')//遇到左括号{S.push(i);//左括号的下标入栈ans[i]=' ';//暂时将对应输出字符串位置改为空格}else if(str[i]==')')//遇到右括号{//栈非空if(S.empty()==false){S.pop();//出一个ans[i]=' ';//将对应输出字符串位置改为空格}//栈空else{ans[i]='?';}}else{ans[i]=' ';//其他字符均没有标记}}//for//已遍历完while(!S.empty()){ans[S.top()]='$';S.pop();}//为了使ans[]输出为字符串,在结尾加/0ans[i]=0;//输出cout<<str<<endl;cout<<ans<<endl;}return 0;
}

• 例2、简单计算器

基于基础的运算符+ - * / ()，实现一个简单的四则运算（带括号）的计算器

思路：中缀表达式转后缀表达
（1）建立两个栈，一个保存运算符，一个保存数字。
（2）表达式首尾添加标记运算符，此运算符的运算优先级最低。
（3）从左到右遍历字符串，遇到运算符a，与栈顶运算符b比较优先级，若a>b或栈空——>a入栈。
（4）若a<b——>b出栈，两个数字出栈，运算结果再入栈。
（5）遇到数字，直接入栈。
（6）遇到左括号，入栈
（7）遇到右括号，一直出栈直到出一个左括号
（8）运算符栈只有人工添加标记运算符，则数字栈为最后结果。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<time.h>
#include<stack>
using namespace std;char str[101];//保存输入字符
int mat[][5]={//运算符优先级矩阵，i>j即mat[i][j]=1,0:人为定义，1-4依次表示加减乘除1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,1,0,0,1,1,1,0,0,
};
stack<int> op;//运算符栈
stack<int> in;//数字栈//获得表达式中下一个元素，函数运行结束时，引用变量reto为true:该元素是一个运算符，保存在retn中；否则，元素是一个数字，保存在引用变量retn中。引用变量i表示遍历到的字符串下标
//reto:ture retn:1~6 +-*/()
void getOp(bool &reto,int &retn,int &i)
{//若遍历到第一个字符串，且栈空，人为添加0号操作符if(i==0&&op.empty()==true){reto=true;retn=0;return;}//若遍历字符为0，表示已遍历完。返回0号操作符if(str[i]==0){reto=true;retn=0;return;}//若遇到数字if(str[i]<='9'&&str[i]>='0'){reto=false;}//遇到运算符else {reto=true;if(str[i]=='+')	retn=1;else if(str[i]=='-')	retn=2;else if(str[i]=='*')	retn=3;else if(str[i]=='/')	retn=4;else if(str[i]=='(')	retn=5;else if(str[i]==')')	retn=6;i++;//跳过此字符return;}retn=0;for(;str[i]<='9'&&str[i]>='0';i++){retn*=10;retn+=str[i]-'0';}return;
}int main()
{cin>>str;//定义函数所需引用变量bool retop;int retnum;int idx=0;//清空栈while(!op.empty()) op.pop();while(!in.empty()) in.pop();//循环遍历表达式字符串while(true){getOp(retop,retnum,idx);//获得表达式中下一个元素//获得数字if(retop==false)in.push(retnum);//获得运算符else                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           {int temp;//可入栈情况：1.栈空 2.栈顶运算符优先级更小 3.遇到(if(mat[retnum][op.top()]==1 || op.empty()==true || retnum==5)op.push(retnum);//遇到)：出两个数，一个运算符，一个（，计算，压栈else if(retnum==6){int ret=op.top();op.pop();//出一个运算符op.pop();//出一个（int b=in.top();in.pop();int a=in.top();in.pop();//计算if(ret==1) temp=a+b;if(ret==2) temp=a-b;if(ret==3) temp=a*b;if(ret==4) temp=a/b;//压栈in.push(temp);}//栈顶不＜=：待入；出两个数，一个运算符，计算，压栈（循环直到可入栈）;最后运算符入栈else{while(mat[retnum][op.top()]==0){int ret=op.top();op.pop();//出一个运算符int b=in.top();in.pop();int a=in.top();in.pop();//计算if(ret==1) temp=a+b;if(ret==2) temp=a-b;if(ret==3) temp=a*b;if(ret==4) temp=a/b;//压栈in.push(temp);}//最后运算符入栈op.push(retnum);}}//结束的标志：str[i]==0即retn=0即op中有两个0if(op.size()==2&&op.top()==0)break;}//结果就是in栈顶元素cout<<in.top();return 0;
}

注：ac不过。。希望有人指点一下。