P1175 表达式的转换

题目简述

给定常规的表达式，将其改写为后缀表达式并把每个中间过程进行的运算结果依次输出

思路

思维难度不大，毕竟数据量比较小，暴力就行了，但码量还是有一点的，代码有点丑，日后有机会可以尝试重新写一遍

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
char s[N];
int len,md[N],kdl;
char _s[N][N];
int cal(int sta){
  int kdl=0;
  for(int i=sta;i;i++){
    if(s[i]=='(')kdl++;
    if(s[i]==')')kdl--;
    if(kdl==0)return i; 
  }
}
void work(int l,int r){
  if(l>r)return ;
  switch(s[l]){
    case '+':{
      for(int i=l+1;i<=r;){
        if(s[i]=='+'||s[i]=='-'){
          work(l+1,i-1);
          _s[1][++len]='+';
          work(i,r);
          return ;
        }
        else {
          if(s[i]=='(')i=cal(i)+1;
          else i++;
        }
      }
      work(l+1,r);
      _s[1][++len]='+';
      return ;
    }
    case '-':{
      for(int i=l+1;i<=r;){
        if(s[i]=='+'||s[i]=='-'){
          work(l+1,i-1);
          _s[1][++len]='-';
          work(i,r);
          return ;
        }
        else {
          if(s[i]=='(')i=cal(i)+1;
          else i++;
        }
      }
      work(l+1,r);
      _s[1][++len]='-';
      return ;
    }
    case '/':{
      for(int i=l+1;i<=r;){
        if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
          work(l+1,i-1);
          _s[1][++len]='/';
          work(i,r);
          return ;
        }
        else {
          if(s[i]=='(')i=cal(i)+1;
          else i++;
        }
      }
      work(l+1,r);
      _s[1][++len]='/';
      return ;
    }
    case '*':{
      for(int i=l+1;i<=r;){
        if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
          work(l+1,i-1);
          _s[1][++len]='*';
          work(i,r);
          return ;
        }
        else {
          if(s[i]=='(')i=cal(i)+1;
          else i++;
        }
      }
      work(l+1,r);
      _s[1][++len]='*';
      return ;
    }
    case '^':{
      for(int i=l+1;i<=r;){
        if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
          work(l+1,i-1);
          _s[1][++len]='^';
          work(i,r);
          return ;
        }
        else {
          if(s[i]=='(')i=cal(i)+1;
          else i++;
        }
      }
      work(l+1,r);
      _s[1][++len]='^';
      return ;
    }
    case '(':{
      work(l+1,cal(l)-1);
      work(cal(l)+1,r);
      return ;
    }
  }
  _s[1][++len]=s[l];
  work(l+1,r);
  return ;
}
int main(){
  scanf("%s",s+1);
  work(1,strlen(s+1));
  for(int i=1;i<=len;i++)cout<<_s[1][i]<<' ';
  puts("");
  for(int i=1;i<=len;i++){
    if(_s[1][i]>='0'&&_s[1][i]<='9'){
      md[++kdl]=_s[1][i]-'0';
      continue;
    }
    switch(_s[1][i]){
      case '+':{
        md[kdl-1]=(md[kdl-1])+(md[kdl]);
        kdl--;
        for(int j=1;j<=kdl;j++)cout<<md[j]<<' ';
        for(int j=i+1;j<=len;j++)cout<<_s[1][j]<<' ';
        cout<<endl;
        break;
      }
      case '-':{
        md[kdl-1]=(md[kdl-1])-(md[kdl]);
        kdl--;
        for(int j=1;j<=kdl;j++)cout<<md[j]<<' ';
        for(int j=i+1;j<=len;j++)cout<<_s[1][j]<<' ';
        cout<<endl;
        break;
      }
      case '*':{
        md[kdl-1]=(md[kdl-1])*(md[kdl]);
        kdl--;
        for(int j=1;j<=kdl;j++)cout<<md[j]<<' ';
        for(int j=i+1;j<=len;j++)cout<<_s[1][j]<<' ';
        cout<<endl;
        break;
      }
      case '/':{
        md[kdl-1]=(md[kdl-1])/(md[kdl]);
        kdl--;
        for(int j=1;j<=kdl;j++)cout<<md[j]<<' ';
        for(int j=i+1;j<=len;j++)cout<<_s[1][j]<<' ';
        cout<<endl;
        break;
      }
      case '^':{
        md[kdl-1]=pow((md[kdl-1]),(md[kdl]));
        kdl--;
        for(int j=1;j<=kdl;j++)cout<<md[j]<<' ';
        for(int j=i+1;j<=len;j++)cout<<_s[1][j]<<' ';
        cout<<endl;
        break;
      }
    }
  }
  return 0;
}