堆棧+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;
    //規(guī)則是，左括號全都入棧，直到找到右括號就全部彈出到第一個左括號
    int flag=0;
    for(auto it=str.begin();it!=str.end();it++){
        if(list.count(*it)>0){
            //此處應當是只將括號入棧
                //在list當中有括號的情況下
            if(bracket.empty()==false){
                //這個意思是匹配上了！！一定要注意兩個狀態(tài)，棧頂和當前
                if(list[bracket.top()]+list[*it]==7)
                    bracket.pop();
                else {
                    if(list[*it]<=3)
                        //左括號全部推入
                        bracket.push(*it);
                    //如果it右部匹配又是右括號就要跳出循環(huán)
                    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");
}


//堆棧括號匹配，主要是不記得括號匹配的規(guī)則了,
int main()
{
    int n;
    unordered_map<char,int> list;
    //只想說這樣匹配太好用了，優(yōu)雅
    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;
    //這仿佛是在尋找數(shù)字和操作符
    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表示已經(jīng)轉(zhuǎn)換？？，最后存成了double型？？
            //flag為1應當表示的是操作符而不是數(shù)字
            flag=1;
        }else{
            if(sign.empty()==false){
                    //比較棧頂?shù)暮彤斍皌emp中的優(yōu)先級
                if(isp[sign.top()]>=osp[temp]){
                    while(sign.empty()==false){
                            //比較堆棧優(yōu)先級和當前操作符優(yōu)先級
                        if(isp[sign.top()]<osp[temp])
                            break;
            //只有棧頂?shù)膬?yōu)先級比較大的時候才可以計算，否則得要符號入棧
                        compute(number,sign);
                    }
                }
            }
            sign.push(temp);
            //操作符入棧，并且表示下一個字符為數(shù)字
            flag=0;
        }
    }
    while(sign.empty()==false){
        compute(number,sign);
    }
    return number.top();
}

//中綴表達式轉(zhuǎn)后綴表達式，最后按照相應規(guī)則處理數(shù)字棧和符號棧
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;
}

棧+隊列實現(xiàn)中綴轉(zhuǎn)后綴，計算后綴表達式

#include <iostream>
#include <32/bits/stdc++.h>
//如何模仿計算器
/*
步驟一：中綴表達式轉(zhuǎn)后綴表達式
設立一個操作符棧，可以臨時存放操作符，設立一個數(shù)組或者隊列，用以存放后綴表達式
步驟二：計算后綴表達式
從左到右掃描后綴表達式，操作數(shù)則入棧，操作符則連續(xù)彈出兩個操作數(shù)
*/
using namespace std;


struct node{
    double num; //操作數(shù)
    char op;   //操作符
    bool flag;  //true表示操作數(shù)，false表示操作符

};

string str;
//處理輸入

stack<node> s; //操作符棧
queue<node> q; //后綴表達式序列
map<char,int> op;  //存儲優(yōu)先級！！

void Change(){
    double num;
    node temp;
    for(int i=0;i<str.size();){
        if(isdigit(str[i])){
            temp.flag=true;  //標記為數(shù)字
            temp.num=str[i++]-'0';  //由于可能是一個百位數(shù)字，先記錄高位
            while(i<str.size()&&isdigit(str[i])){
                temp.num=temp.num*10+(str[i]-'0');
                i++;
            }
            q.push(temp);
        }else{
            temp.flag=false;
            //標記是操作符，只要棧頂元素比該操作符優(yōu)先級高，就把棧頂元素彈到表達式中
            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);  //操作數(shù)直接壓棧
        else{
            temp2=s.top().num; //先彈出來的是第二操作數(shù)
            s.pop();
            temp1=s.top().num; //彈出第一操作數(shù)
            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();  //中綴轉(zhuǎn)后綴
        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表示操作數(shù)
};
string str;

stack<node> s; //操作符棧
queue<node> q;//后綴表達式序列
map<char,int> op;  //map存儲符號優(yōu)先級

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';
            //多位數(shù)怎么辦
            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{
                //第二操作數(shù)
            temp2=s.top().num;
            s.pop();
            //彈出第一操作數(shù)
            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();  //中綴轉(zhuǎn)后綴
        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;
}

任務調(diào)度：優(yōu)先隊列+string處理和unordermap

//優(yōu)先隊列進行任務調(diào)度
/*
輸入 
輸入包含多組測試數(shù)據(jù)。

每組第一行輸入一個整數(shù)n（n<100000），表示有n個任務。

接下來n行，每行第一個表示前序任務，括號中的任務為若干個后序任務，表示只有在前序任務完成的情況下，后序任務才能開始。若后序為NULL則表示無后繼任務。

輸出 
輸出調(diào)度方式，輸出如果有多種適合的調(diào)度方式，請輸出字典序最小的一種。

*/
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;

struct Task{
    string name;
    int level;
    //定義優(yōu)先規(guī)則
    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函數(shù)
    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;
}