質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.89%

C言語 二分木を生成する

受付中

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 2,873

score 11

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+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;
}


実行結果

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/24 15:36

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

    キャンセル

  • 2016/06/24 16:50

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

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/24 11:45

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

    キャンセル

  • 2016/06/24 11:49

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

    キャンセル

  • 2016/06/24 12:36

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

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

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

    キャンセル

0

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.89%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る