AOJ 2740 みさわさんの根付き木

問題文

2つの根付き木A,Bが文字列で与えられる.(|A|, |B| <= 1000)
根付き木の各ノードは値と左右の子(or nullptr)を持つ.
二分木を合成してできる二分木を入力と同じ形式にして出力せよ.

みさわさんの根付き木 | Aizu Online Judge

解法

構文解析. 書き始める前に以下のページを読んだ.
構文解析 Howto · GitHub

BNF っぽく書くと
tree := "" | '(' tree ')' '[' number ']' '(' tree ')'
number := ﾃｷﾄｳ
になるのでパーサーを書く.

自分は二分木データ構造を作ってから A, B を各々二分木にし,愚直に合成してから文字列に戻す, という解き方をした.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3655784

#include "bits/stdc++.h"

using namespace std;

// パースする文字列
string s;
// 次に読み始める位置
int pos;

// 二分木ノード
struct Node
{
    int val;
    Node *l, *r;
};

// tr := (tr)[num](tr)

// 整数
int number()
{
    int ret = 0;
    while (isdigit(s[pos]))
    {
        ret *= 10;
        ret += s[pos] - '0';
        pos++;
    }
    return ret;
}

// パースして二分木のノードを返す
Node *misawa()
{
    if (s[pos] == ')')
    {
        // 空ノード
        return nullptr;
    }
    pos++;             // (
    auto l = misawa(); // left child
    pos++;             // )
    pos++;             // [
    auto v = number();
    pos++;             // ]
    pos++;             // (
    auto r = misawa(); // right child
    pos++;             // )
    Node *node = new Node;
    node->val = v;
    node->l = l;
    node->r = r;
    return node;
}

// 二分木a, b を合成
Node *rec(Node *a, Node *b)
{
    Node *ret = new Node;
    ret->val = a->val + b->val;
    ret->l = nullptr;
    ret->r = nullptr;
    if (a->l && b->l)
    {
        ret->l = rec(a->l, b->l);
    }
    if (a->r && b->r)
    {
        ret->r = rec(a->r, b->r);
    }
    return ret;
}

// 二分木を文字列に変換
string recstr(Node *node)
{
    if (node == nullptr)
        return "";
    string ret = "";
    ret += "(" + recstr(node->l) + ")";
    ret += "[" + to_string(node->val) + "]";
    ret += "(" + recstr(node->r) + ")";
    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    string a, b;
    cin >> a >> b;
    s = a;
    pos = 0;
    auto at = misawa();
    s = b;
    pos = 0;
    auto bt = misawa();
    auto ret = rec(at, bt);
    cout << recstr(ret) << endl;
}

感想

パーサーより二分木がバグりそう