表达式计算4 题解

嗯。。。表达式计算的又一道类模板

做这类题，其实就相当于在搞一个大模拟的题目。

我们需要注意的是：因为有多余的括号出现，所以我们最好在一开始把多余的括号去掉，防止中途计算出现问题。

其次，就是需要注意计算的顺序，对于此题，我们应该先算括号，再算乘方，然后按出现顺序算乘除，最后再按出现顺序算加减。

我的代码非常长，因为全程大模拟/xk

不过，其中有很多地方只是稍微改了一点点，应该可读/xk

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=31;
inline int calc(string x){//计算表达式x的值
    int sta[N],top=0;int fa[N],val[N],len=x.size();
    for(int i=0;i<len;++i){
        fa[i]=i;val[i]=0;
    }
    //去一层括号
    for(int i=0;i<len;++i){
        if(x[i]=='('){
            sta[++top]=i;
        }else if(x[i]==')'){
            int l=sta[top--];
            string y="";
            for(int j=l+1;j<i;++j){
                y+=x[j];
            }
            int w=calc(y);
            for(int j=l;j<=i;++j){
                fa[j]=l;
            }
            val[l]=w;
        }
    }
    //计算数字
    for(int i=0;i<len;++i){
        if(x[i]>='0'&&x[i]<='9'&&fa[i]==i){
            int w=0,r=len-1;
            for(int j=i;j<len;++j){
                if(x[j]<'0'||x[j]>'9'){
                    r=j-1;
                    break;
                }
                w=w*10+(x[j]-'0');
            }
            for(int j=i;j<=r;++j){
                fa[j]=i;
           }
            val[i]=w;
            i=r;
        }
    }
    //乘方
    for(int i=0;i<len;++i){
        if(x[i]=='^'&&fa[i]==i){
            int l=0,r=len-1;
            for(int j=i-1;~j;--j){
                if(fa[j]!=fa[i-1]){
                    l=j+1;
                    break;
                }
            }
            for(int j=i+1;j<len;++j){
                if(fa[j]!=fa[i+1]){
                    r=j-1;
                    break;
                }
            }
            int w=pow(val[fa[l]],val[fa[r]]);
            for(int j=l;j<=r;++j){
                fa[j]=l;
            }
            val[l]=w;
        }
    }
    //乘除
    for(int i=0;i<len;++i){
        if(x[i]=='*'&&fa[i]==i){
            int l=0,r=len-1;
            for(int j=i-1;~j;--j){
                if(fa[j]!=fa[i-1]){
                    l=j+1;
                    break;
                }
            }
            for(int j=i+1;j<len;++j){
                if(fa[j]!=fa[i+1]){
                    r=j-1;
                    break;
                }
            }
            int w=val[fa[l]]*val[fa[r]];
            for(int j=l;j<=r;++j){
                fa[j]=l;
            }
            val[l]=w;
        }
        if(x[i]=='/'&&fa[i]==i){
            int l=0,r=len-1;
            for(int j=i-1;~j;--j){
                if(fa[j]!=fa[i-1]){
                    l=j+1;
                    break;
                }
            }
            for(int j=i+1;j<len;++j){
                if(fa[j]!=fa[i+1]){
                    r=j-1;
                    break;
                }
            }
            int w=val[fa[l]]/val[fa[r]];
            for(int j=l;j<=r;++j){
                fa[j]=l;
            }
            val[l]=w;
        }
    }
    //加减
    for(int i=0;i<len;++i){
        if(x[i]=='+'&&fa[i]==i){
            int l=0,r=len-1;
            for(int j=i-1;~j;--j){
                if(fa[j]!=fa[i-1]){
                    l=j+1;
                    break;
                }
            }
            for(int j=i+1;j<len;++j){
                if(fa[j]!=fa[i+1]){
                    r=j-1;
                    break;
                }
            }
            int w=val[fa[l]]+val[fa[r]];
            for(int j=l;j<=r;++j){
                fa[j]=l;
            }
            val[l]=w;
        }
        if(x[i]=='-'&&fa[i]==i){
            int l=0,r=len-1;
            for(int j=i-1;~j;--j){
                if(fa[j]!=fa[i-1]){
                    l=j+1;
                    break;
                }
            }
            for(int j=i+1;j<len;++j){
                if(fa[j]!=fa[i+1]){
                    r=j-1;
                    break;
                }
            }
            int w=val[fa[l]]-val[fa[r]];
            for(int j=l;j<=r;++j){
                fa[j]=l;
            }
            val[l]=w;
        }
    }
    return val[0];
}
inline string rebuild(string x){//去掉多余括号
    int sta[31],top=0;bool flag[31];
    int len=x.size();
    for(int i=0;i<len;++i){
        if(x[i]=='('){
            sta[++top]=i;
        }else if(x[i]==')'){
            if(top)--top;
            else flag[i]=1;
        }
    }
    for(int i=1;i<=top;++i){
        flag[sta[i]]=1;
    }
    string y="";
    for(int i=0;i<len;++i){
        if(!flag[i]){
            y+=x[i];
        }
    }
    return y;
}
int main(){
    string x;
    cin>>x;
    printf("%d",calc(rebuild(x)));
    return 0;
}