#include <iostream>
#include <stack>
#include <queue>
#include <malloc.h>
#define STR_MAX 100
template <typename DataType> struct BTNode {
DataType value;
struct BTNode *lchild;
struct BTNode *rchild;
explicit BTNode(DataType x) : value(x), lchild(NULL), rchild(NULL) {}
};
// seperate the text into two segements by a char
// sample: A,B --(',')--> A B
int seperateStr(const char *str, char *recv_1, char *recv_2, const char sign) {
if (!str) return -1;
for (int i = 0; str[i] != sign; i++) {
if (recv_1)
recv_1[i] = str[i];
}
if (recv_1)
recv_1[i] = '\0';
i++;
for (int j = 0 ; str[i] != '\0'; i++, j++) {
if (recv_2)
recv_2[j] = str[i];
}
if (recv_2)
recv_2[j] = '\0';
return 0;
}
// Translate the string to a BTree
// sample:A(B(,G),C(D(F),E))
// output:
// A
// / \
// B C
// \ / \
// G D E
// /
// F
BTNode<char>* StrToBTree(const char *str, BTNode<char> *&T) {
if (!str) return NULL;
std::stack <BTNode<char>*> st;
int flag = -1;
BTNode<char> *p = NULL;
if (T) {
free(T); T = NULL;
}
for (int i = 0; str[i] != '\0'; i++) {
switch(str[i]) {
case '(':
if (p) {
flag = 0;// start_left_child
st.push(p);
p = NULL;
}
break;
case ')':
st.pop();
break;
case ',':
flag = 1; // start_right_child
break;
default:
p = new BTNode<char>(str[i]);
if (!T) T = p; // save the original root
else {
switch (flag) {
case 0:
st.top()->lchild = (BTNode*)p;
break;
case 1:
st.top()->rchild = (BTNode*)p;
break;
default:
break;
}
}
break;
}
}
return T;
}
// Translate the BTree to a string
// sample:
// A
// / \
// B C
// \ / \
// G D E
// /
// F
// output:A(B(,G),C(D(F),E))
char* BTreeToStr(BTNode<char> *T, char *str) {
if (!str) return NULL;
if (!T) return NULL;
static int i = 0;
str[i++] = T->value;
if (T->lchild || T->rchild)
str[i++] = '(';
BTreeToStr((BTNode<char>*)T->lchild, str);
if (T->rchild)
str[i++] = ',';
BTreeToStr((BTNode<char>*)T->rchild, str);
if (T->lchild || T->rchild)
str[i++] = ')';
str[i] = 0;
return str;
}
int main () {
BTNode<char> *T = NULL;
char str[STR_MAX];
StrToBTree("A(B(D,E),C(F,G))", T); // input your test cases
printf(BTreeToStr(T, str));
printf("\n");
return 0;
}
