ZJNU 1069 表达式的转换——中级

栈运用的模板题，对于符号进行出入栈操作，每次与栈顶的符号进行优先级判断，得出第一行后缀表达式。

在其后的化简计算中，每次用一个特殊符号（代码中使用了'?'）代替原来的计算结果引用，并开一个数组表示每次的计算结果，之后搜索到'?'时用这个结果进行代入计算。

直到只剩下一个数字，停止程序。

#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
int rplans[100010];
char ans[100010];
bool mns[100010];
int lv(char c){
    switch(c){
        case '+':return 1;
        case '-':return 1;
        case '*':return 2;
        case '/':return 2;
        case '^':return 3;
        case '(':return 0;
        case ')':return 0;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    stack<char> skc;
    char c;
    int fh=0,fs=0,cnt=0,i,j,k,a1,a2;
    while((c=getchar())!=EOF&&c!='\n'){
        if(c>='0'&&c<='9'){
            if(fs){
                mns[cnt]=true;
                fs=0;
            }
            else
                mns[cnt]=false;
            ans[cnt++]=c;
            fh=0;
        }
        else{
            if(c==')'){
                while(skc.top()!='('){
                    ans[cnt++]=skc.top();
                    skc.pop();
                }
                skc.pop();
            }
            else{
                if(c=='('||c=='^')
                    skc.push(c);
                else{
                    if(c=='-'&&fh)
                        fs=1;
                    else{
                        while(!skc.empty()&&lv(skc.top())>=lv(c)){
                            ans[cnt++]=skc.top();
                            skc.pop();
                        }
                        skc.push(c);
                    }
                }
                fh=1;
            }
        }
    }
    while(!skc.empty()){
        ans[cnt++]=skc.top();
        skc.pop();
    }
    cout<<ans[0];
    for(i=1;i<cnt;i++)
        cout<<' '<<ans[i];
    cout<<endl;
    for(i=0;i<(cnt-1)/2;i++){
        for(j=2;j<cnt;j++)
            if(ans[j]=='+'||ans[j]=='-'||ans[j]=='*'||ans[j]=='/'||ans[j]=='^')
                break;
        for(k=j-1;k>=0;k--)
            if(ans[k]>='0'&&ans[k]<='9'||ans[k]=='!')
                break;
        if(ans[k]!='!')
            a1=(ans[k]-'0')*(mns[k]?-1:1);
        else
            a1=rplans[k];
        ans[k]='?';
        for(k--;k>=0;k--)
            if(ans[k]>='0'&&ans[k]<='9'||ans[k]=='!')
                break;
        if(ans[k]!='!')
            a2=(ans[k]-'0')*(mns[k]?-1:1);
        else
            a2=rplans[k];
        ans[k]='?';
        if(ans[j]=='+')
            rplans[j]=a2+a1;
        else if(ans[j]=='-')
            rplans[j]=a2-a1;
        else if(ans[j]=='*')
            rplans[j]=a2*a1;
        else if(ans[j]=='/')
            rplans[j]=a2/a1;
        else
            rplans[j]=pow(a2,a1);
        ans[j]='!';
        for(j=k=0;j<cnt;j++){
            if(ans[j]!='?'){
                if(k)
                    cout<<' ';
                if(ans[j]=='!')
                    cout<<rplans[j];
                else
                    cout<<ans[j];
                k=1;
            }
        }
        cout<<endl;
    }
    return 0;
}