Submission #1216399


Source Code Expand

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
     
    struct tree{
      char c;
      bool f;
      tree *l,*r;
      tree(){}
      tree(char c):c(c){l=r=NULL;f=1;}
      tree(char c,tree *l,tree *r):c(c),l(l),r(r){f=0;}
      tree(const tree& t){
        c=t.c;
        f=t.f;
        l=t.l;
        r=t.r;
      }
    };
     
    string dfs(tree v){
      //cout<<v.c<<endl;
      if(v.f) return string(1,v.c);
      string res;
      //cout<<(v.l)->c<<v.c<<(v.r)->c<<endl;
      //return res;
      res+=dfs(*(v.r));
      res+=dfs(*(v.l));
      //cout<<res<<endl;
      return res+string(1,v.c);
    }
     
    int calc(string s){
      stack<int> t;
      for(int i=0;i<(int)s.size();i++){
        if(isdigit(s[i])) t.push(s[i]-'0');
        else{
          int r=t.top();t.pop();
          int l=t.top();t.pop();
          if(s[i]=='+') t.push(l+r);
          if(s[i]=='-') t.push(l-r);
          if(s[i]=='*') t.push(l*r);
        }
      }
      return t.top();
    }
    int calc2(string s){
      queue<int> t;
      for(int i=0;i<(int)s.size();i++){
        if(isdigit(s[i])) t.push(s[i]-'0');
        else{
          int r=t.front();t.pop();
          int l=t.front();t.pop();
          if(s[i]=='+') t.push(l+r);
          if(s[i]=='-') t.push(l-r);
          if(s[i]=='*') t.push(l*r);
        }
      }
      return t.front();
    }
     
    signed main(){
      string s;
      cin>>s;
      stack<tree> t;
      for(int i=0;i<(int)s.size();i++){
        //cout<<s[i]<<endl;
        if(isdigit(s[i])) t.push(tree(s[i]));
        else{
          tree r=t.top();t.pop();
          tree l=t.top();t.pop();
          //cout<<l.c<<s[i]<<r.c<<endl;
          t.push(tree(s[i],new tree(l),new tree(r)));
        }
      }
      //puts("c");
      tree root=t.top();
      //cout<<(root.l)->c<<root.c<<(root.r)->c<<end
      string u;
      queue<tree> q;
      q.push(root);
      while(!q.empty()){
        tree p=q.front();q.pop();
        u+=p.c;
        if(!p.f){
          q.push(*(p.l));
          q.push(*(p.r));
        }
      }
      reverse(u.begin(),u.end());
      cout<<u<<endl;
      string a=s,b=u;
      sort(a.begin(),a.end());
      sort(b.begin(),b.end());
      assert(a==b);
      //cout<<calc(s)<<endl<<calc2(u)<<endl;
      assert(calc(s)==calc2(u));
      //cout<<u<<endl;
      return 0;
    }

Submission Info

Submission Time
Task F - 逆ポーランド記法
User beet
Language C++14 (GCC 5.4.1)
Score 200
Code Size 2467 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 96
Set Name Test Cases
All 00_sample_01.txt, 00_sample_02.txt, 10_random_all_01.txt, 10_random_all_02.txt, 10_random_all_03.txt, 10_random_all_04.txt, 10_random_all_05.txt, 10_random_all_06.txt, 10_random_all_07.txt, 10_random_all_08.txt, 10_random_all_09.txt, 10_random_all_10.txt, 10_random_all_11.txt, 10_random_all_12.txt, 10_random_all_13.txt, 10_random_all_14.txt, 10_random_all_15.txt, 10_random_all_16.txt, 10_random_all_17.txt, 10_random_all_18.txt, 10_random_all_19.txt, 10_random_all_20.txt, 10_random_all_21.txt, 10_random_all_22.txt, 10_random_all_23.txt, 10_random_all_24.txt, 10_random_all_25.txt, 10_random_all_26.txt, 10_random_all_27.txt, 10_random_all_28.txt, 10_random_all_29.txt, 10_random_all_30.txt, 10_random_all_31.txt, 10_random_all_32.txt, 10_random_all_33.txt, 10_random_all_34.txt, 10_random_all_35.txt, 10_random_all_36.txt, 10_random_all_37.txt, 10_random_all_38.txt, 10_random_all_39.txt, 10_random_all_40.txt, 10_random_all_41.txt, 10_random_all_42.txt, 10_random_all_43.txt, 10_random_all_44.txt, 10_random_all_45.txt, 10_random_all_46.txt, 10_random_all_47.txt, 10_random_all_48.txt, 10_random_all_49.txt, 10_random_all_50.txt, 22_small_51.txt, 22_small_52.txt, 22_small_53.txt, 22_small_54.txt, 22_small_55.txt, 22_small_56.txt, 22_small_57.txt, 22_small_58.txt, 22_small_59.txt, 22_small_60.txt, 22_small_61.txt, 22_small_62.txt, 22_small_63.txt, 22_small_64.txt, 22_small_65.txt, 22_small_66.txt, 22_small_67.txt, 22_small_68.txt, 22_small_69.txt, 22_small_70.txt, 33_alternation_71.txt, 33_alternation_72.txt, 33_alternation_73.txt, 33_alternation_74.txt, 33_alternation_75.txt, 33_alternation_76.txt, 33_alternation_77.txt, 33_alternation_78.txt, 33_alternation_79.txt, 33_alternation_80.txt, 34_oneside_81.txt, 34_oneside_82.txt, 34_oneside_83.txt, 34_oneside_84.txt, 34_oneside_85.txt, 34_oneside_86.txt, 34_oneside_87.txt, 34_oneside_88.txt, 34_oneside_89.txt, 34_oneside_90.txt, 44_mul_91.txt, 44_mul_92.txt, 44_mul_93.txt, 44_mul_94.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 1 ms 256 KB
00_sample_02.txt AC 1 ms 256 KB
10_random_all_01.txt AC 1 ms 256 KB
10_random_all_02.txt AC 1 ms 256 KB
10_random_all_03.txt AC 1 ms 256 KB
10_random_all_04.txt AC 1 ms 256 KB
10_random_all_05.txt AC 1 ms 256 KB
10_random_all_06.txt AC 1 ms 256 KB
10_random_all_07.txt AC 1 ms 256 KB
10_random_all_08.txt AC 1 ms 256 KB
10_random_all_09.txt AC 1 ms 256 KB
10_random_all_10.txt AC 1 ms 256 KB
10_random_all_11.txt AC 1 ms 256 KB
10_random_all_12.txt AC 1 ms 256 KB
10_random_all_13.txt AC 1 ms 256 KB
10_random_all_14.txt AC 1 ms 256 KB
10_random_all_15.txt AC 1 ms 256 KB
10_random_all_16.txt AC 1 ms 256 KB
10_random_all_17.txt AC 1 ms 256 KB
10_random_all_18.txt AC 1 ms 256 KB
10_random_all_19.txt AC 1 ms 256 KB
10_random_all_20.txt AC 1 ms 256 KB
10_random_all_21.txt AC 1 ms 256 KB
10_random_all_22.txt AC 1 ms 256 KB
10_random_all_23.txt AC 1 ms 256 KB
10_random_all_24.txt AC 1 ms 256 KB
10_random_all_25.txt AC 1 ms 256 KB
10_random_all_26.txt AC 1 ms 256 KB
10_random_all_27.txt AC 1 ms 256 KB
10_random_all_28.txt AC 1 ms 256 KB
10_random_all_29.txt AC 1 ms 256 KB
10_random_all_30.txt AC 1 ms 256 KB
10_random_all_31.txt AC 1 ms 256 KB
10_random_all_32.txt AC 1 ms 256 KB
10_random_all_33.txt AC 1 ms 256 KB
10_random_all_34.txt AC 1 ms 256 KB
10_random_all_35.txt AC 1 ms 256 KB
10_random_all_36.txt AC 1 ms 256 KB
10_random_all_37.txt AC 1 ms 256 KB
10_random_all_38.txt AC 1 ms 256 KB
10_random_all_39.txt AC 1 ms 256 KB
10_random_all_40.txt AC 1 ms 256 KB
10_random_all_41.txt AC 1 ms 256 KB
10_random_all_42.txt AC 1 ms 256 KB
10_random_all_43.txt AC 1 ms 256 KB
10_random_all_44.txt AC 1 ms 256 KB
10_random_all_45.txt AC 1 ms 256 KB
10_random_all_46.txt AC 1 ms 256 KB
10_random_all_47.txt AC 1 ms 256 KB
10_random_all_48.txt AC 1 ms 256 KB
10_random_all_49.txt AC 1 ms 256 KB
10_random_all_50.txt AC 1 ms 256 KB
22_small_51.txt AC 1 ms 256 KB
22_small_52.txt AC 1 ms 256 KB
22_small_53.txt AC 1 ms 256 KB
22_small_54.txt AC 1 ms 256 KB
22_small_55.txt AC 1 ms 256 KB
22_small_56.txt AC 1 ms 256 KB
22_small_57.txt AC 1 ms 256 KB
22_small_58.txt AC 1 ms 256 KB
22_small_59.txt AC 1 ms 256 KB
22_small_60.txt AC 1 ms 256 KB
22_small_61.txt AC 1 ms 256 KB
22_small_62.txt AC 1 ms 256 KB
22_small_63.txt AC 1 ms 256 KB
22_small_64.txt AC 1 ms 256 KB
22_small_65.txt AC 1 ms 256 KB
22_small_66.txt AC 1 ms 256 KB
22_small_67.txt AC 1 ms 256 KB
22_small_68.txt AC 1 ms 256 KB
22_small_69.txt AC 1 ms 256 KB
22_small_70.txt AC 1 ms 256 KB
33_alternation_71.txt AC 1 ms 256 KB
33_alternation_72.txt AC 1 ms 256 KB
33_alternation_73.txt AC 1 ms 256 KB
33_alternation_74.txt AC 1 ms 256 KB
33_alternation_75.txt AC 1 ms 256 KB
33_alternation_76.txt AC 1 ms 256 KB
33_alternation_77.txt AC 1 ms 256 KB
33_alternation_78.txt AC 1 ms 256 KB
33_alternation_79.txt AC 1 ms 256 KB
33_alternation_80.txt AC 1 ms 256 KB
34_oneside_81.txt AC 1 ms 256 KB
34_oneside_82.txt AC 1 ms 256 KB
34_oneside_83.txt AC 1 ms 256 KB
34_oneside_84.txt AC 1 ms 256 KB
34_oneside_85.txt AC 1 ms 256 KB
34_oneside_86.txt AC 1 ms 256 KB
34_oneside_87.txt AC 1 ms 256 KB
34_oneside_88.txt AC 1 ms 256 KB
34_oneside_89.txt AC 1 ms 256 KB
34_oneside_90.txt AC 1 ms 256 KB
44_mul_91.txt AC 1 ms 256 KB
44_mul_92.txt AC 1 ms 256 KB
44_mul_93.txt AC 1 ms 256 KB
44_mul_94.txt AC 1 ms 256 KB