JAG Contest 2016 Domestic C - みさわさんの根付き木

jag2016-domestic.contest.atcoder.jp

誤って書いた記事を消してしまったので再投稿です．

問題文

省略

解法(反転して表示)

LL(1)による再帰構文解析を知っていると特に思考をせず木構造に直すことができる． 木に落としたらマージをするが，これは再帰でやるのが実装が楽でおすすめ．平衡二分木をmerge-splitベースで実装したことがあるとイメージがつきやすいかも． 余談ですが，構文解析，「次に来る文字が△◎×だったら～」みたいな処理を結構アドホックだと思っていたら，first集合やfollow集合とかいう概念があったりするので，そういうのを学んでみて，強く意識すると迷ったり漏れが発生することが少なくなるかも．

ソース

#include <bits/stdc++.h>
using namespace std;
 
 
string S;
int p;
struct T{
    int v;
    T *l,*r; 
    T(){
        l = r = NULL;
    }
}; 
 
T *merge(T *a,T *b){
    if( a == NULL || b == NULL ) return NULL;
    T *r = new T();
    r->v = a->v + b->v;
    r->l = merge(a->l,b->l);
    r->r = merge(a->r,b->r);
    return r;
}
void view(T *x){
    
    if( !x ) return;
    cout << "(";
    view(x->l);
    cout << ")";
    cout << "[";
    cout << x->v;
    cout << "]";
    cout << "(";
    view(x->r);
    cout << ")";
    
}
 
T* expr(){
    if( S[p] != '(' ) return NULL;
    T *res = new T();
    //←の子
    p++;
    res->l = expr();
    p++;
    
    p++;
    int x = 0;
    while( S[p] >= '0' && S[p] <= '9' ) x = x * 10 + S[p++] - '0';
    res->v = x;
    p++;
    //→の子
    p++;
    res->r = expr();
    p++;
    return res;
}
int main(){
    string s,t;
    cin >> s >> t;
    S = s;
    p = 0;
    auto one = expr();
    S = t;
    p = 0;
    auto two = expr();
    view(merge(one,two));
    cout << endl;
}