プログラマ専用SNS ミクプラ

コード:

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

コード:

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