AOJ2740 Rooted Tree for Misawa-san

問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2740&lang=jp

方針を間違えるとやばそう. うまく実装できてよかった.

一度連結リストで管理するグラフを復元して, 元の表現に戻す処理をするみたいなのが思いつくがそれをする必要はなく, 再帰関数で次のように処理を行う.

部分木の根を探す. 今回だと括弧の深さが0でなおかつ'[' + (数字) + ']'であるもの
その頂点を境界として, 右部分木と左部分木にパースする. なお, 両端の'(' ')'を除外しておく.
そして, '(' + (左部分木の結果) + ')' + (根の情報) + '(' + (右部分木の結果) + ')' を返すことを繰り返す.
これにより再帰関数をするだけになる.
もし部分木に根が存在しないならば, それは存在しない頂点なので, 何も返さなくてよい.

提出コード

string dfs(string s, string t){

  int cnt=0;
  int l1 = -1, r1=-1;
  for(int i=0; i<s.size(); i++){

    if(cnt == 0 && s[i]=='['){
      l1 = i;
      while(i<s.size() && s[i] != ']') i++;
      r1 = i;
      break;
    }
    if(s[i] == '(') cnt++;
    else if(s[i] == ')')cnt--;
  }
  
  cnt = 0;
  int l2=-1, r2=-1;
  for(int i=0; i<t.size(); i++){
    if(cnt == 0 && t[i]=='['){
      l2 = i;
      while(i<t.size() && t[i] != ']') i++;
      r2 = i;
      break;
    }
    if(t[i] == '(') cnt++;
    else if(t[i] == ')') cnt--;
  }

  if(l1 == -1 || l2 == -1) return "";

  int num1 = 0, num2 = 0;
  for(int i=l1+1; i<=r1-1; i++) num1 = num1*10 + s[i]-'0';
  for(int i=l2+1; i<=r2-1; i++) num2 = num2*10 + t[i]-'0';

  string ret = '[' + to_string(num1+num2) + ']';

  string nsl="", nsr="", ntl="", ntr="";
  for(int i=1; i<l1-1; i++) nsl += s[i];
  for(int i=r1+2; i<s.size()-1; i++) nsr += s[i];
  for(int i=1; i<l2-1; i++) ntl += t[i];
  for(int i=r2+2; i<t.size()-1; i++) ntr += t[i];
  return '(' + dfs(nsl, ntl) + ')' + ret + '(' + dfs(nsr, ntr) + ')';
}
int main()
{
  //cin.tie(0);
  //ios::sync_with_stdio(false);
  cout << fixed << setprecision(8);

  string s, t; cin >> s >> t;

  cout << dfs(s, t) << endl;
  return 0;
}