#include <bits/stdc++.h>

using namespace std;

typedef char Element;

struct Node;

typedef struct Node *BTree;

struct Node{

    Element data;

    struct Node *lchild;

    struct Node *rchild; 

};

BTree NewNode(Element x)

{

    BTree p=(BTree)malloc(sizeof(struct Node));

    p->data=x;

    p->lchild=NULL;

    p->rchild=NULL;

    return p;

}

//广义表创建二叉树     A(B(D,),C(E,F(,H)))

BTree Create_BTree(char s[])

{

    int k=0,top=-1;

    BTree path[100],p;

    for(int i=0;s[i]!='\0';i++){

        switch(s[i]){

            case '(':    path[++top]=p;    k=1;    break;

            case ',':    k=2;    break;

            case ')':    top--;    break;

        }

        if(isalpha(s[i])){

            p=NewNode(s[i]);

            if(k==1)

                path[top]->lchild=p;

            else if(k==2)

                path[top]->rchild=p;

        }

    }    

    return path[0];

}

//递归创建二叉树    A(B(D,),C(E,F(,H)))

int Find(char s[],int left,int right)

{

    int k=0;

    for(int i=left;i<=right;i++){

        if(s[i]=='(')

            k++;

        if(s[i]==')')

            k--;

        if(s[i]==',' && k==1)

            return i;

    }    

    return left;

} 

BTree Create_BTree(char s[],int left,int right)

{

    int mid;

    if(left>right)

        return NULL;

    mid=Find(s,left,right);

    BTree root=NewNode(s[left]);

    root->lchild=Create_BTree(s,left+2,mid-1);

    root->rchild=Create_BTree(s,mid+1,right-1);

    return root; 

}

//先序扩展创建二叉树    ABD...C..

BTree Create_BTree()

{

    BTree root;

    char c=getchar();

    if(c=='.')

        return NULL;

    root=NewNode(c);

    root->lchild=Create_BTree();

    root->rchild=Create_BTree();

    return root; 

}

//根据先序和中序遍历确定二叉树    先序：abdfgceh    中序：fdgbache

int Find(char in[],int start,int end,char x)

{

    for(int i=start;i<=end;i++)

        if(in[i]==x)

            return i;

    return -1;

} 

BTree Create_BTree(char pre[],int s1,int e1,char in[],int s2,int e2)

{

    BTree root=NewNode(pre[s1]);

    int k=Find(in,s2,e2,pre[s1]);

    if(k!=s2)    

        root->lchild=Create_BTree(pre,s1+1,s1+(k-s2),in,s2,k-1);

    if(k!=e2)

        root->rchild=Create_BTree(pre,s1+(k-s2)+1,e1,in,k+1,e2);

    return root; 

}