堆栈+ordermap使用括号匹配
#include <iostream>
#include <string>
#include <unordered_map>
#include <stack>
using namespace std;
void dispose(string str,unordered_map<char,int> list){
stack<char> bracket;
//规则是，左括号全都入栈，直到找到右括号就全部弹出到第一个左括号
int flag=0;
for(auto it=str.begin();it!=str.end();it++){
if(list.count(*it)>0){
//此处应当是只将括号入栈
//在list当中有括号的情况下
if(bracket.empty()==false){
//这个意思是匹配上了！！一定要注意两个状态，栈顶和当前
if(list[bracket.top()]+list[*it]==7)
bracket.pop();
else {
if(list[*it]<=3)
//左括号全部推入
bracket.push(*it);
//如果it右部匹配又是右括号就要跳出循环
else
break;
}
}
else{
//如果当前是空的话，若是立马遇见错括号可以直接跳楼了
bracket.push(*it);
if(list[*it]>3)
break;
}
}
}
//这里是左括号多余的情况
if(bracket.empty()==false)
flag=0;
else
flag=1;
if(flag==0)
printf("no\n");
else
printf("yes\n");
}
//堆栈括号匹配，主要是不记得括号匹配的规则了,
int main()
{
int n;
unordered_map<char,int> list;
//只想说这样匹配太好用了，优雅
list['{']=1;
list['[']=2;
list['(']=3;
list[')']=4;
list[']']=5;
list['}']=6;
while(cin>>n){
string temp;
for(int i=0;i<n;i++){
cin>>temp;
dispose(temp,list);
}
}
return 0;
}
堆栈使用简单计算器
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
int str_to_int(const string &string_temp){
int temp;
stringstream stream(string_temp);
stream>>temp;
return temp;
}
void compute(stack<double> &number,stack<string> &sign){
double b=number.top();
//终于知道了，取值只能靠top！！，pop相当于清除
number.pop();
double a=number.top();
number.pop();
string op=sign.top();
sign.pop();
if(op=="+"){
//果然是按照算法一步步来的
number.push(a+b);
}else if(op=="-"){
number.push(a-b);
}
else if(op=="*"){
number.push(a*b);
}else{
number.push(a/b);
}
}
double dispose(unordered_map<string,int> isp,unordered_map<string,int> osp,string str){
stack<double> number;
stack<string> sign;
int flag=0;
//这仿佛是在寻找数字和操作符
while(str.empty()==false){
string temp;
int pos=str.find(" ");
if(pos!=string::npos){
temp=temp+str.substr(0,pos);
str.erase(0,pos+1);
}
else{
//找不到空格的时候，直接可以取最后剩余作为字符串
temp=str;
str.clear();
}
if(flag==0){
number.push(str_to_int(temp));
//fflag表示已经转换？？，最后存成了double型？？
//flag为1应当表示的是操作符而不是数字
flag=1;
}else{
if(sign.empty()==false){
//比较栈顶的和当前temp中的优先级
if(isp[sign.top()]>=osp[temp]){
while(sign.empty()==false){
//比较堆栈优先级和当前操作符优先级
if(isp[sign.top()]<osp[temp])
break;
//只有栈顶的优先级比较大的时候才可以计算，否则得要符号入栈
compute(number,sign);
}
}
}
sign.push(temp);
//操作符入栈，并且表示下一个字符为数字
flag=0;
}
}
while(sign.empty()==false){
compute(number,sign);
}
return number.top();
}
//中缀表达式转后缀表达式，最后按照相应规则处理数字栈和符号栈
int main()
{
string temp;
while(getline(cin,temp)){
if(temp!="0"){
unordered_map<string,int> isp,osp;
isp["+"]=1;
isp["-"]=1;
isp["*"]=2;
isp["/"]=2;
osp["+"]=1;
osp["-"]=1;
osp["*"]=2;
osp["/"]=2;
double result=dispose(isp,osp,temp);
printf("%.2f\n",result);
temp.clear();
}else{
break;
}
}
return 0;
}
栈+队列实现中缀转后缀，计算后缀表达式
#include <iostream>
#include <32/bits/stdc++.h>
//如何模仿计算器
/*
步骤一：中缀表达式转后缀表达式
设立一个操作符栈，可以临时存放操作符，设立一个数组或者队列，用以存放后缀表达式
步骤二：计算后缀表达式
从左到右扫描后缀表达式，操作数则入栈，操作符则连续弹出两个操作数
*/
using namespace std;
struct node{
double num; //操作数
char op; //操作符
bool flag; //true表示操作数，false表示操作符
};
string str;
//处理输入
stack<node> s; //操作符栈
queue<node> q; //后缀表达式序列
map<char,int> op; //存储优先级！！
void Change(){
double num;
node temp;
for(int i=0;i<str.size();){
if(isdigit(str[i])){
temp.flag=true; //标记为数字
temp.num=str[i++]-'0'; //由于可能是一个百位数字，先记录高位
while(i<str.size()&&isdigit(str[i])){
temp.num=temp.num*10+(str[i]-'0');
i++;
}
q.push(temp);
}else{
temp.flag=false;
//标记是操作符，只要栈顶元素比该操作符优先级高，就把栈顶元素弹到表达式中
while(!s.empty()&&op[str[i]]<=op[s.top().op]){
q.push(s.top());
s.pop();
}
temp.op=str[i];
//压入新的操作符
s.push(temp);
i++;
}
}
while(!s.empty()){
//若操作符中还有操作符，就得都弹入后缀表达式序列
q.push(s.top());
s.pop();
}
}
double Cal(){
//计算后缀表达式
double temp1,temp2;
node cur,temp;
while(!q.empty()){
cur=q.front(); //cur记录队首元素
q.pop();
if(cur.flag==true) s.push(cur); //操作数直接压栈
else{
temp2=s.top().num; //先弹出来的是第二操作数
s.pop();
temp1=s.top().num; //弹出第一操作数
s.pop();
temp.flag=true;
//临时记录草锁住
if(cur.op=='+') temp.num=temp1+temp2;
else if(cur.op=='-') temp.num=temp1-temp2;
else if(cur.op=='*') temp.num=temp1*temp2;
else if(cur.op=='/') temp.num=temp1/temp2;
s.push(temp);
}
}
return s.top().num;
//栈顶元素为后缀表达式的值
}
int main()
{
op['+']=op['-']=1;
op['*']=op['/']=2;
while(getline(cin,str),str!="0"){
for(auto it=str.end();it!=str.begin();it--){
if(*it==' ') str.erase(it); //去除掉表达式中空格
}
while(!s.empty()) s.pop(); //初始化栈
Change(); //中缀转后缀
printf("%.2f\n",Cal());
}
cout << "Hello world!" << endl;
return 0;
}
栈+队列计算，包括括号版
48*((70-65)-43)+8*1
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <cctype>
#include <map>
using namespace std;
struct node{
int num;
char op;
bool flag;
//true表示操作数
};
string str;
stack<node> s; //操作符栈
queue<node> q;//后缀表达式序列
map<char,int> op; //map存储符号优先级
void Change(){
int num;
node temp;
for(int i=0;i<str.size();){
//括号处理出的问题
if(str[i]=='('){
temp.flag=false;
temp.op=str[i];
s.push(temp);
i++;
}else if(str[i]==')'){
while(s.top().op!='('){
q.push(s.top());
s.pop();
}
s.pop();
i++;
}
else if(isdigit(str[i])){
temp.flag=true;
temp.num=str[i++]-'0';
//多位数怎么办
while(i<str.size()&&isdigit(str[i])){
temp.num=temp.num*10+(str[i]-'0');
i++;
}
//真正的队列压入
q.push(temp);
}else{
temp.flag=false;
while(!s.empty()&&op[str[i]]<=op[s.top().op]){
q.push(s.top());
s.pop();
}
temp.op=str[i];
//真正的操作符压入
s.push(temp);
i++;
}
}
while(!s.empty()){
q.push(s.top());
s.pop();
}
}
int Cal(){
int temp1,temp2;
node cur,temp;
while(!q.empty()){
cur=q.front();
q.pop();
if(cur.flag==true)
//一个栈多用
s.push(cur);
else{
//第二操作数
temp2=s.top().num;
s.pop();
//弹出第一操作数
temp1=s.top().num;
s.pop();
temp.flag=true;
//temp1,temp2生成
if(cur.op=='+')
temp.num=temp1+temp2;
else if(cur.op=='-')
temp.num=temp1-temp2;
else if(cur.op=='*')
temp.num=temp1*temp2;
else if(cur.op=='/')
temp.num=temp1/temp2;
s.push(temp);
}
}
return s.top().num;
//栈顶元素为最后值
}
int main()
{
op['+']=op['-']=1;
op['*']=op['/']=2;
while(getline(cin,str)){
while(!s.empty()) s.pop(); //初始化栈
Change(); //中缀转后缀
printf("%d\n",Cal());
}
return 0;
}
另一种直接写法，不会栈溢出
#include<cstdio>
#include<map>
#include<cstring>
#include<ctype.h>
#include<stack>
#include<queue>
using namespace std;
struct node{
int data;
char op;
int flag;
}Node;
stack<char> s;
queue<node> q;
char str[1010];
map<char,int> m;
int main(){
m['+']=1;
m['-']=1;
m['(']=0;
m['*']=2;
m['/']=2;
scanf("%s",str);
int len=strlen(str);
for(int i=0;i<len;++i){
if(str[i]>='0'&&str[i]<='9'){
int sum=0;
while(str[i]>='0'&&str[i]<='9'){
sum=sum*10+str[i]-'0';
i++;
}
Node.data=sum;
Node.flag=1;
q.push(Node);
i--;
}
else if(!(str[i]>='0'&&str[i]<='9')){
if(str[i]=='(')
s.push(str[i]);
else if(str[i]==')'){
while(s.top()!='('){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
s.pop();
}else if(s.empty()||m[str[i]]>m[s.top()]){
s.push(str[i]);
}else{
while(!s.empty()&&m[str[i]]<=m[s.top()]){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
s.push(str[i]);
}
}
//printf("2");
}
while(!s.empty()){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
stack<int> s1;
int sum=0;
while(!q.empty()){
node no=q.front();
if(no.flag==1){
s1.push(no.data);
}else{
int a=s1.top();
s1.pop();
int b=s1.top();
s1.pop();
if(no.op=='+'){
sum=a+b;
}else if(no.op=='-'){
sum=b-a;
}else if(no.op=='*'){
sum=a*b;
}else{
sum=b/a;
}
s1.push(sum);
}
q.pop();
}
printf("%d",s1.top());
return 0;
}
队列使用
#include <iostream>
#include <queue>
#include <iterator>
using namespace std;
int main(){
queue<int> q;
for(int i=1;i<=5;i++){
q.push(i);
//入队
}
if(q.empty()){
cout<<q.front()<<" ";
}
//输出队首1和队尾5
cout<<q.back()<<endl;
if(q.empty()){
q.pop();
}
return 0;
}
任务调度：优先队列+string处理和unordermap
//优先队列进行任务调度
/*
输入
输入包含多组测试数据。
每组第一行输入一个整数n（n<100000），表示有n个任务。
接下来n行，每行第一个表示前序任务，括号中的任务为若干个后序任务，表示只有在前序任务完成的情况下，后序任务才能开始。若后序为NULL则表示无后继任务。
输出
输出调度方式，输出如果有多种适合的调度方式，请输出字典序最小的一种。
*/
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
struct Task{
string name;
int level;
//定义优先规则
friend bool operator < (const Task &t1,const Task &t2){
if(t1.level!=t2.level)
return t1.level>t2.level;
else return t1.name>t2.name;
}
};
//使用引用表示要修改
void dispose(string str,priority_queue<Task> &task,unordered_map<string,int> &list){
string first;
int pos;
int firstlevel;
//从输入当中分理出任务
pos=str.find('(');
first=str.substr(0,pos);
str.erase(0,pos+1);
//list.count只能是1或0，,1表示存在，0表示没有，类似find
//而find返回的则是元素的迭代器
if(list.count(first)==0){
Task newtask;
newtask.name=first;
newtask.level=0;
task.push(newtask);
firstlevel=list[first]=0;
}
else{
firstlevel=list[first];
}
//str也可以使用empty函数
while(str.empty()==false){
string last;
pos=str.find(',');
if(str.find(',')==string::npos){
pos=str.find(')');
last=str.substr(0,pos);
str.clear();
}else{
last=str.substr(0,pos);
str.erase(0,pos+1);
}
if(last!="NULL"){
Task newtask;
newtask.name=last;
newtask.level=firstlevel+1;
list[last]=newtask.level;
task.push(newtask);
}
}
}
int main()
{
int n;
while(cin>>n){
priority_queue<Task> task;
//hash对应，且不排序
unordered_map<string,int> list;
string temp;
for(int i=0;i<n;i++){
cin>>temp;
dispose(temp,task,list);
}
while(task.empty()==false){
cout<<task.top().name;
task.pop();
if(!task.empty()){
cout<<" ";
}
}
list.clear();
}
return 0;
}
