ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1001 Binary Tree Intersection And Union

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001

ツリーが2つ与えられます。その2つの和集合か積集合を求める問題です。


・解法
まず与えられた文字列に対して構文解析をし、2つのツリーを作ります。
私はこのような構造体を用いてツリーを作りました。

struct Tree{
vector left,right;
};

あとは再帰的に2つのツリーを見ていき、和・積集合を求めていけばよいです。


ソースコード

#include<iostream>
#include<string>
#include<vector>
using namespace std;

struct Tree{
  vector<Tree> left,right;
};

int pos1,pos2;
char op;
string s1,s2;
Tree null;

Tree parse1(){
  Tree res;
  if(s1[pos1]=='(')pos1++;
  if(s1[pos1]!=','){
    res.left.push_back(parse1());
  }
  if(s1[pos1]==',')pos1++;
  if(s1[pos1]!=')'){
    res.right.push_back(parse1());
  }
  if(s1[pos1]==')')pos1++;
  return res;
}

Tree parse2(){
  Tree res;
  if(s2[pos2]=='(')pos2++;
  if(s2[pos2]!=','){
    res.left.push_back(parse2());
  }
  if(s2[pos2]==',')pos2++;
  if(s2[pos2]!=')'){
    res.right.push_back(parse2());
  }
  if(s2[pos2]==')')pos2++;
  return res;
}

string dfs_i(Tree t1, Tree t2){
  string res = ","; 
  if(t1.left.size()!=0 && t2.left.size()!=0){
    res = "(" + dfs_i(t1.left[0], t2.left[0]) + res;
  }
  else res = "(" + res;
  if(t1.right.size()!=0 && t2.right.size()!=0){
    res = res + dfs_i(t1.right[0], t2.right[0]) + ")";
  }
  else res = res + ")";
  return res;
}

string dfs_u(Tree t1, Tree t2){
  string res = ",";
  Tree tmp1, tmp2;
  if(t1.left.size()!=0 || t2.left.size()!=0){
    tmp1 = (t1.left.size()!=0) ? t1.left[0] : null;
    tmp2 = (t2.left.size()!=0) ? t2.left[0] : null;
    res = "(" + dfs_u(tmp1, tmp2) + res;
  }
  else res = "(" + res;
  if(t1.right.size()!=0 || t2.right.size()!=0){
    tmp1 = (t1.right.size()!=0) ? t1.right[0] : null;
    tmp2 = (t2.right.size()!=0) ? t2.right[0] : null;
    res = res + dfs_u(tmp1, tmp2) + ")";
  }
  else res = res + ")";
  return res;
}

int main(){
  while(cin >> op){
    cin >> s1 >> s2;
    pos1 = pos2 = 0;
    Tree t1 = parse1();
    Tree t2 = parse2();
    string ans = "";
    if(op=='i'){
      ans = dfs_i(t1, t2);
    }
    if(op=='u'){
      ans = dfs_u(t1, t2);
    }
    cout << ans << endl;
  }
  return 0;
}