Submission #1215873

---

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

Judge Result