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

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<stack>
  5 using namespace std;
  6 int rplans[100010];
  7 char ans[100010];
  8 bool mns[100010];
  9 int lv(char c){
 10     switch(c){
 11         case ‘+‘:return 1;
 12         case ‘-‘:return 1;
 13         case ‘*‘:return 2;
 14         case ‘/‘:return 2;
 15         case ‘^‘:return 3;
 16         case ‘(‘:return 0;
 17         case ‘)‘:return 0;
 18     }
 19 }
 20 int main(){
 21     ios::sync_with_stdio(0);
 22     cin.tie(0);cout.tie(0);
 23     stack<char> skc;
 24     char c;
 25     int fh=0,fs=0,cnt=0,i,j,k,a1,a2;
 26     while((c=getchar())!=EOF&&c!=‘\n‘){
 27         if(c>=‘0‘&&c<=‘9‘){
 28             if(fs){
 29                 mns[cnt]=true;
 30                 fs=0;
 31             }
 32             else
 33                 mns[cnt]=false;
 34             ans[cnt++]=c;
 35             fh=0;
 36         }
 37         else{
 38             if(c==‘)‘){
 39                 while(skc.top()!=‘(‘){
 40                     ans[cnt++]=skc.top();
 41                     skc.pop();
 42                 }
 43                 skc.pop();
 44             }
 45             else{
 46                 if(c==‘(‘||c==‘^‘)
 47                     skc.push(c);
 48                 else{
 49                     if(c==‘-‘&&fh)
 50                         fs=1;
 51                     else{
 52                         while(!skc.empty()&&lv(skc.top())>=lv(c)){
 53                             ans[cnt++]=skc.top();
 54                             skc.pop();
 55                         }
 56                         skc.push(c);
 57                     }
 58                 }
 59                 fh=1;
 60             }
 61         }
 62     }
 63     while(!skc.empty()){
 64         ans[cnt++]=skc.top();
 65         skc.pop();
 66     }
 67     cout<<ans[0];
 68     for(i=1;i<cnt;i++)
 69         cout<<‘ ‘<<ans[i];
 70     cout<<endl;
 71     for(i=0;i<(cnt-1)/2;i++){
 72         for(j=2;j<cnt;j++)
 73             if(ans[j]==‘+‘||ans[j]==‘-‘||ans[j]==‘*‘||ans[j]==‘/‘||ans[j]==‘^‘)
 74                 break;
 75         for(k=j-1;k>=0;k--)
 76             if(ans[k]>=‘0‘&&ans[k]<=‘9‘||ans[k]==‘!‘)
 77                 break;
 78         if(ans[k]!=‘!‘)
 79             a1=(ans[k]-‘0‘)*(mns[k]?-1:1);
 80         else
 81             a1=rplans[k];
 82         ans[k]=‘?‘;
 83         for(k--;k>=0;k--)
 84             if(ans[k]>=‘0‘&&ans[k]<=‘9‘||ans[k]==‘!‘)
 85                 break;
 86         if(ans[k]!=‘!‘)
 87             a2=(ans[k]-‘0‘)*(mns[k]?-1:1);
 88         else
 89             a2=rplans[k];
 90         ans[k]=‘?‘;
 91         if(ans[j]==‘+‘)
 92             rplans[j]=a2+a1;
 93         else if(ans[j]==‘-‘)
 94             rplans[j]=a2-a1;
 95         else if(ans[j]==‘*‘)
 96             rplans[j]=a2*a1;
 97         else if(ans[j]==‘/‘)
 98             rplans[j]=a2/a1;
 99         else
100             rplans[j]=pow(a2,a1);
101         ans[j]=‘!‘;
102         for(j=k=0;j<cnt;j++){
103             if(ans[j]!=‘?‘){
104                 if(k)
105                     cout<<‘ ‘;
106                 if(ans[j]==‘!‘)
107                     cout<<rplans[j];
108                 else
109                     cout<<ans[j];
110                 k=1;
111             }
112         }
113         cout<<endl;
114     }
115     return 0;
116 }