俺のアルゴリズム改善点あったら教えてくれ。

[ikarinoseiryuu]

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

typedef struct bintree{
        char* word;
        struct bintree* left;
        struct bintree* right;

}Bin;


void restore(Bin** bin, char* tree, int start){
int i, a,  num_left, num_right;
char s[100];
num_left = 0;
num_right = 0;
for(i=start; num_left - num_right != 1 || i== start + 1; i++){
  if(tree[i] == '(')
    num_left+= 1;
  if(tree[i] == ')')
    num_right+=1;
  if(num_left - num_right == 0)
   return;
}
a = 0;
 for(i; tree[i] != '('; i++){
   s[a] = tree[i];
   a++;
 }
 s[a] = '\0';
 if(*bin == NULL){
  *bin = malloc(sizeof(Bin));
  memset(*bin, 0, sizeof(Bin));
  (*bin)->word =  malloc(strlen(s));
  strcpy((*bin)->word, s);

 }

 restore(&((*bin)->left), tree, start+1);
 restore(&((*bin)->right), tree, i);



}


void show(Bin* bin){
 if(bin == NULL)
 return;

 else{
  show(bin->left);
  printf("%s\n", bin->word);
  show(bin->right);


}



}



int main(int argc, char** argv){
Bin* bin;
bin = 0;
restore(&bin, argv[1], 0);
printf("\n");
show(bin);









return 0;
}

２分木を次のように現わした

（左側の要素　自分の要素　右側の要素）

で、左（右）の要素がNULLだった場合は、()であらわす。
例えば、rootノードがlionで、左側がkoala 右側がdog
だった場合は、
((()koala())lion(()dog()))
っていう風に表現される。
で、この木のdogの右に、catを追加した場合は、
次のようになる。
((()koala())lion(()dog(()cat())))

ってなる。

そこで、この表現から、木を再構築するアルゴリズムを書いたわけです。
引数に、この表現が渡されて、それを二分木に再構築するわけです。




エラー処理はしてないけど、そこ以外のところで改善点がほしいです。たとえば、もっと高速、効率的なのがあるとか。

[みけCAT]

エラー処理はしてないけど、そこ以外のところで改善点がほしいです。

まずは無駄な空行を消して、インデントを整えるといいと思います。

[ikarinoseiryuu]

＞＞みけCATさん
もっと本質的なところでお願いします。
アルゴリズムの改善点であってソースコードのきれいさの問題ではないので。

[みけCAT]

「自分の要素」の左側の部分を読み捨てているので、そこを繰り返し読む分の時間の無駄が生じるはずです。

今回の入力をBNFで表現すると

コード:

<tree>    ::= <element>
<element> ::= "()" | "(" <element> <word> <element> ")"
<word>    ::= 省略

となり、これをもとに同じ場所を繰り返し読まないプログラムを作ると、例えば

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct bintree {
	char* word;
	struct bintree* left;
	struct bintree* right;

} Bin;

/* bin : 次の要素を出力するポインタ tree : 木の文字列表現 戻り値 : 次に読み込むべき場所 */
const char* restore(Bin** bin, const char* tree) {
	/* ここで*treeは(のはず */
	if (*tree != '(') {
		fprintf(stderr, "syntax error : ( expected, got %c\n", *tree);
		exit(1);
	}
	tree++;
	if(*tree == ')') {
		/* NULL要素 */
		*bin = NULL;
		return tree + 1;
	} else {
		const char *start_point;
		size_t count;
		*bin = malloc(sizeof(Bin));
		if (*bin == NULL) {
			fputs("malloc failed\n", stderr);
			exit(1);
		}
		/* 左側の要素を読み込む */
		tree = restore(&(*bin)->left, tree);
		/* 自分の要素を読み込む */
		start_point = tree;
		for (count = 0; *tree != '(' && *tree != '\0'; tree++) count++;
		if (*tree == '\0') {
			fputs("syntax error : expected ( not found\n", stderr);
			exit(1);
		}
		(*bin)->word = malloc(count + 1);
		if ((*bin)->word == NULL) {
			fputs("malloc falied for word\n", stderr);
			exit(1);
		}
		strncpy((*bin)->word, start_point, count);
		(*bin)->word[count] = '\0';
		/* 右側の要素を読み込む */
		tree = restore(&(*bin)->right, tree);
		/* ここで*treeは')'のはず */
		if (*tree != ')') {
			fprintf(stderr, "syntax error : ) expected, got %c\n", *tree);
			exit(1);
		}
		return tree + 1;
	}
}

void show(Bin* bin){
	if(bin != NULL) {
		show(bin->left);
		printf("%s\n", bin->word);
		show(bin->right);
	}
}

void release(Bin* bin) {
	if (bin != NULL) {
		release(bin->left);
		release(bin->right);
		free(bin->word);
		free(bin);
	}
}

int main(int argc, char** argv){
	Bin* bin;
	if(argc < 2) return 1;
	bin = 0;
	restore(&bin, argv[1]);
	printf("\n");
	show(bin);
	release(bin);
	return 0;
}

のようになります。

[ikarinoseiryuu]

＞＞みけCATさん
ありがとうございました。