7-2 栈实现表达式求值

发布时间 2023-11-23 20:51:17作者: Misa先生

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

const int N=100010;

string split(string s){

    string ss;

    for(int i=0;i<s.size();i++){

        if(s[i]==32) continue;

        ss+=char(s[i]);

    }

    return ss;

}

 

bool ck1(string s){

    int cnt=0;

    for(int i=0;i<s.size();i++){

        if(s[i]=='(') cnt++;

        else if(s[i]==')') cnt--;

    }

    return  cnt==0;

}

 

bool ck2(string s){

    for(int i=0;i<s.size();i++){

        if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){

            if(i==0||i==s.size()-1||i&&(s[i-1]=='+'||s[i-1]=='-'||s[i-1]=='*'||s[i-1]=='/')){

                return 0;

            }

        }

    }

    return 1;

}

 

int pri(char ch){return ch=='*'||ch=='/'?2:1;}

char ch[N];

int cnt;

string cg(string s){

    string ss;

    for(int i=0;i<s.size();i++){

        if(s[i]>='0'&&s[i]<='9'){

            ss+=char(s[i]);

        }else{

            if(s[i]=='('){

                ch[cnt++]='(';

            }else if(s[i]==')'){

                while(ch[cnt-1]!='('){

                    ss+=ch[--cnt];

                }

                cnt--;

            }else{

                char c=char(s[i]);

                if(cnt>0&&pri(c)<=pri(ch[cnt-1])){

                    while(cnt>0&&ch[cnt-1]!='('&&pri(c)<=pri(ch[cnt-1])){

                        ss+=ch[--cnt];

                    }

                }

                ch[cnt++]=c;

            }

        }

    }

    while(cnt>0){

        ss+=ch[--cnt];

    }

    return ss;

}

 

int op(int x,int y,char ch){

    if(ch=='+') return x+y;

    else if(ch=='-') return x-y;

    else if(ch=='*') return x*y;

    else return x/y;

}

int a[N],ct;

int op(string s){

    for(int i=0;i<s.size();i++){

        if(s[i]>='0'&&s[i]<='9'){

            a[ct++]=s[i]-48;

        }

        else{

            int x=a[ct-2],y=a[ct-1];

            ct-=2;

            a[ct++]=op(x,y,char(s[i]));

        }

    }

    return a[0];

}

 

int main(){

    string s;

    getline(cin,s);

     

    s=split(s);

 

    if(!ck1(s)){

        cout<<"ERROR:缺少括号";

        return 0;

    }

     

    if(!ck2(s)){

        cout<<"ERROR:表达式缺操作数";

        return 0;

    }

     

    string ss=cg(s);

    cout<<ss<<endl;

     

    cout<<op(ss);

     

return 0;

 

}