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

佚名 4年前 (2020-01-18) 随笔 1520人围观抢沙发百度已收录

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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