cafelier@SRM

AOJ1001: Binary Tree Intersection And Union

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001

import std.conv;
import std.range;
import std.stdio;

class Tree
{
   static Tree parse(ref string s)
   {
      if( s[0] != '(' )
         return null;

      assert(s[0]=='('); s = s[1..$];
      Tree l = parse(s);
      assert(s[0]==','); s = s[1..$];
      Tree r = parse(s);
      assert(s[0]==')'); s = s[1..$];
      return new Tree(l, r);
   }

   static Tree inter(Tree x, Tree y)
   {
      if( x is null || y is null )
         return null;
      return new Tree(inter(x.left, y.left), inter(x.right, y.right));
   }

   static Tree uni(Tree x, Tree y)
   {
      if( x is null ) return y;
      if( y is null ) return x;
      return new Tree(uni(x.left, y.left), uni(x.right, y.right));
   }

   this(Tree l, Tree r)
   {
      left = l;
      right = r;
   }

   override string toString()
   {
      return "(" ~ (left is null ? "" : left.toString())
           ~ "," ~ (right is null ? "" : right.toString())
           ~ ")";
   }

   Tree left, right;
}

void main()
{
   string line;
   while( !(line=readln()).empty )
   {
      string[] tok = line.split();
      Tree t1 = Tree.parse(tok[1]);
      Tree t2 = Tree.parse(tok[2]);
      writeln( (tok[0]=="u" ? &Tree.uni : &Tree.inter)(t1, t2) );
   }
}

一応クラスを作る必要がある例がでてきました。ツリーを作っています。writeln などにクラスのインスタンスを渡すと toString() が呼ばれます。