栈

栈混洗

有A,B,S，三个栈，初始化一个排列在B中，B中的元素，通过栈S到达栈A中，
A中可以得到不同的排列。
计数：A中排列的个数
记为排列的长度是的时候的个数，若中已经有个元素，则中剩余个元素，
这时候的个数是 ,枚举,
这就是卡特兰数列，

判断栈A的排列是否能由栈B经过栈S得到
模拟栈B，pop()的过程。

bool is(int *A,int *B,int n){
    //A   栈底[1,n]栈顶。
    //B    栈顶[1...n]栈底
    stack<int>S;
    int t=1;
    for(int i=1;i<=n;i++){
        S.push(B[i]);
        while(!S.empty()&&t<=n&&S.top()==A[t]){
            S.pop();t++;
        }
    }
    return S.empty();
}

栈的运用：计算器
处理出优先级表。

中缀表达式

template<typename T>
struct calculate{
    const char p[9][9]={
    {'>','>','<','<','<','<','<','>','>'},
    {'>','>','<','<','<','<','<','>','>'},
    {'>','>','>','>','<','<','<','>','>'},
    {'>','>','>','>','<','<','<','>','>'},
    {'>','>','>','>','>','<','<','>','>'},
    {'>','>','>','>','>','>',' ','>','>'},
    {'<','<','<','<','<','<','<','=',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {'<','<','<','<','<','<','<',' ','='}
    };
    const char a[9]={'+','-','*','/','^','!','(',')','\0'};
    int id(char c){for(int i =0;i<9;i++)if(c==a[i])return i;}
    stack<T>Int;
    stack<char>Char;
    void Read(int index,char* s){
        if(isdigit(s[index-1])){
            T x=Int.top();Int.pop();
            x=x*10+s[index]-'0';
            Int.push(x);
        }else Int.push(s[index]-'0');
    }
    int power(int x,int y){
        int ans=1;
        for(;y>0;y>>=1,x=x*x)if(y&1)ans=ans*x;
        return ans;
    }
    void cal(char c){
        if(c=='!'){
            if(Int.empty()){
                puts("1 erro");
                exit(0);
            }
            T x=Int.top();Int.pop();
            T ans=1;
            for(int i =1;i<=x;i++)ans*=i;
            Int.push(ans);return;
        }
        if((int)Int.size()<2){
            puts("2 erro");
            exit(0);
        }
        T y=Int.top();Int.pop();
        T x=Int.top();Int.pop();
        switch (c)
        {   
            case '+':x+=y;break;
            case '-':x-=y;break;
            case '*':x*=y;break;
            case '/':{
                if(y==0){
                    puts("3 erro");
                    exit(0);
                }
                x/=y;break;
            }
            case '^':x=power(x,y);break;
            default:break;
        }
        Int.push(x);
    }
    void Switch(char c){
        int y=id(c);
        while(!Char.empty()){
            char b=Char.top();
            int x=id(b);
            if(p[x][y]=='='){Char.pop();return;} 
            if(p[x][y]=='<'){Char.push(c);return;}  
            if(p[x][y]=='>'){
                cal(b);Char.pop();
                continue;
            }
            if(p[x][y]==' '){Char.push(c);return;}
        }
    }
    T work(char* s){
        int n=strlen(s);
        Char.push('\0');
        if(isdigit(s[0]))Int.push(s[0]-'0');
        else{
            if(s[0]=='-')Int.push(0);
            Char.push(s[0]);
        }
        for(int i=1;i<=n;i++){
            if(isdigit(s[i]))Read(i,s);
            else {
                if(s[i]=='+'&&(s[i-1]=='-'||s[i-1]=='('))continue;
                if(s[i]=='-'&&(s[i-1]=='+'||s[i-1]=='('))Int.push(0);
                Switch(s[i]);
            }
        }
        if(!Char.empty())return O("4 erro");
        if((int)Int.size()!=1)return O("5 erro");
        return Int.top();
    }
};

逆波兰表达式(RPN)