Submission #705189

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

int const INF = 1<<29;

struct tree; typedef tree* tree_ptr;

struct tree {
  tree_ptr lch, rch;
  int num;
  tree()
    : lch(NULL), rch(NULL), num(-INF) { }
};

void consume(string& S, char expected) {
  if(S[0] == expected) {
    S = S.substr(1);
    return;
  }
  cout << S << ", " << expected << endl;
  assert(0);
}

bool consume_if(string& S, char expected) {
  if(S[0] == expected) {
    consume(S, expected);
    return true;
  }
  else {
    return false;
  }
}

int read_num(string& S) {
  stringstream ss(S);
  int x; ss >> x;
  ss >> S;
  return x;
}

void make_tree(string& S, tree_ptr curr) {
  if(consume_if(S, '(')) {
    tree_ptr lch = new(tree);
    curr->lch = lch;
    make_tree(S, lch);
    consume(S, ')');
    
    consume(S, '[');
    curr->num = read_num(S);
    consume(S, ']');
    
    consume(S, '(');
    tree_ptr rch = new(tree);
    curr->rch = rch;
    make_tree(S, rch);
    consume(S, ')');
    return;
  }
}

void dfs(tree* ptr1, tree* ptr2) {
  if(ptr1->num == -INF || ptr2->num == -INF) { return; }
  
  if(ptr1->lch && ptr2->lch) {
    cout << "(";
    dfs(ptr1->lch, ptr2->lch);
    cout << ")";
  }
  cout << "[" << (ptr1->num + ptr2->num) << "]";
  if(ptr1->rch && ptr2->rch) {
    cout << "(";
    dfs(ptr1->rch, ptr2->rch);
    cout << ")";
  }
}

int main() {

  string a; cin >> a;
  string b; cin >> b;
  
  tree_ptr atree = new(tree);
  tree_ptr btree = new(tree);
  
  make_tree(a, atree);
  make_tree(b, btree);

  dfs(atree, btree);
  cout << endl;
  
  return 0;
}

Submission Info

Judge Result