栈实现的四则运算

栈实现的四则运算

#include<bits/stdc++.h>
using namespace std;

const int add_length=10;
const int init_length=100;

/*

用类模板使得代码变简洁 

*/
template<typename ElemType>
struct myStack{
    int length;
    int size;
    ElemType *base;
    ElemType *top;
    myStack(){
        size=init_length;
        length=0;
        top=base=(ElemType*) malloc (size * sizeof(ElemType));
    }
    void push(ElemType x){
        ElemType *head;
        if(this->length==this->size)
        {
            head=(ElemType*) realloc(this->base,(this->size+add_length)*sizeof(ElemType));
            this->base=head;
            this->top=head+this->length;
            this->size+=add_length;
        }
        *(this->top++)=x;
        this->length++;
    }
    ElemType gettop(){
        if(this->top!=this->base) return *(this->top-1);
        else return -1;
    }
    ElemType pop(){
        if(top==base) return -1;
        this->top--;
        this->length--;
    }
    bool empty(){
        return this->length==0;
    }
};

string  init(string s){
    string temp;
    for(int i=s.size();i>=0;i--)
    {
        char ch=s[i];
        if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') 
            s=s.substr(0,i)+" "+s[i]+" "+s.substr(i+1);
    }
    return s;
}

const char priority[7][7] =
    {
        { '>','>','<','<','<','>','>' },
        { '>','>','<','<','<','>','>' },
        { '>','>','>','>','<','>','>' },
        { '>','>','>','>','<','>','>' },
        { '<','<','<','<','<','=','0' },
        { '>','>','>','>','0','>','>' },
        { '<','<','<','<','<','0','=' },
    };

bool is_OP(char ch)
{
    return ((ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'));
}

int get(char a)
{
    if(a=='+') return 0;
    if(a=='-') return 1;
    if(a=='*') return 2;
    if(a=='/') return 3;
    if(a=='(') return 4;
    if(a==')') return 5;
    if(a=='#') return 6;
}

char Precede(char a,char b)
{
    int aa=get(a);
    int bb=get(b);
    return priority[aa][bb];
}
int Operate(int a,int ch,int b)
{
    int ans;
    if(ch=='*') ans=a*b;
    if(ch=='+') ans=a+b;
    if(ch=='-') ans=b-a;
    if(ch=='/') ans=b/a;
    return ans;
}
int solve()
{
    myStack<char> op;
    myStack<int> st;

    string s;
    cin>>s;
    s+="#";
    s = init(s);

    stringstream ss(s);
    cout<<s<<endl;

    string c;
    ss>>c;
    op.push('#');
    while(c!="#" || op.gettop()!='#')
    {
        if(!is_OP(c[0])) {
            stringstream temp(c);
            int num;
            temp>>num;
            st.push(num);
            ss>>c;
        }else
        {

            switch(Precede(op.gettop(),c[0])){
                case '<': op.push(c[0]); ss>>c; break;
                case '=': op.pop(); ss>>c;break;
                case '>': 
                {
                    int a=st.gettop(); st.pop();
                    int b=st.gettop(); st.pop();
                    char theta = op.gettop(); op.pop();
                    st.push(Operate(a,theta,b));
                }
            }
        }
    }
    return st.gettop();
}

int main()
{
    int ans=solve();
    cout<<ans<<endl;
    return 0;
}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注