C言語 二分木を生成する

Question

scanfで <<-,1,->,2,<-,3,->> と入力して、それを二分木にする関数を作っているんですが、scanfで読み込むために宣言したcharの配列buffを解析する関数がわからないので教えてほしいです。

※ <,,~>が一つの節点を表していて、- は子の節点がないことを意味します。

Answer 1

正規表現でやってみた(Cだとちょっと面倒かしら...)

#include <iostream>
#include <string>
#include <regex>

using namespace std;

struct node {
  node* left;
  string value;
  node* right;
};

node* parse(const string& str) {
  node* result = new node();
  regex re(R"_(<(<.*>|-),([^<>,]+),(<.*>|-)>)_");
  smatch match;
  if ( regex_match(str, match, re) ) {
    result->left  = match.str(1) == "-" ? nullptr : parse(match.str(1));
    result->value = match.str(2);
    result->right = match.str(3) == "-" ? nullptr : parse(match.str(3));
  } else {
    result->left  = nullptr;
    result->value = str;
    result->right = nullptr;
  }
  return result;
}

void print(node* p) {
  if ( p ) {
    cout << (p->left ? " left ":"(null)");
    cout << " [" << p->value << "] ";
    cout << (p->left ? "right ":"(null)");
    cout << endl;
  } else {
    cout << "(null)\n";
  }
}

int main() try {
  node* root = parse("<<-,1,->,2,<-,3,->>");
  print(root);
  print(root->left);
  print(root->right);
} catch ( const regex_error& err ) {
  cout << err.code() << ':' << err.what() << endl;
}

Comments

[Zuishin]

ああ、よく見たら一つ一つのノードがカンマで区切られてるわけじゃないんですね。
これは確かに正規表現を使わない方が楽かもしれません。
episteme さんすみませんでした。
そしてお見事です。

[episteme]

おもっきし手を抜いたパーサです。

「ノード は "<ノード,数,ノード>" または "-" である」を正規表現にして、
ノード中のノードを見つけたら再帰。
#てか”見たまんま”ですねー

Answer 2

構文解析というのは、それ自体がかなり手間のかかる作業です。

とはいえ、この規模の問題だとそこまで規模も大きくならないので、再帰的下向き構文解析のようなものを手で書いても、じゅうぶん書ける範囲です。

スクリプト言語を作る場合など、構文自体が巨大なものになる場合は、構文解析器を作るツールを活用するのがいいでしょう。C/C++の場合はyacc/bisonあたりが定番ですし、C#用のものも存在します。

Answer 3

正規表現使ったらいいんじゃないですか？

Comments

[episteme]

正規表現を再帰的に適用せんならんだろけど...うまくいくかしら...

[Zuishin]

カンマでスプリットしてリストに突っ込んで再帰でもループでも。
構文解析はそれが一番楽です。

[Zuishin]

木を作るのには普通はノードとなるオブジェクトや構造体を作ってそれを繋いでいくんですが、この事例のように二分木で大きさが分かっている場合にはもっと簡単な方法が使えます。

まずはノードの数(カンマの数からわかるはずです)を数えて十分な大きさの配列を用意し、そこに埋めていくだけです。
配列の要素 0 はルートを表し、1 と2 は 0 の子、3 と 4 は1 の子、5 と 6 は 2 の子という風に、添え字をと節の位置が 1 対 1 対応しますので、位置を簡単に計算でき、極めて高速に処理できます。

これを使うと、ノードの親子関係をたどらなくても処理中のノードをどこに保存すればいいかわかるので、再帰を使わず簡単なループで処理できます。