# define m 3              /* 樹的度數*/
# define MAXSIZE 20       /* 樹的孩子表示法對應的數組大小*/
# define BMAXSIZE 50      /*樹的括號表示對應的數組大小*/
typedef char datatype;    /* 樹中結點值的類型*/
typedef struct node {     /*樹的孩子表示法中結點的類型*/
    datatype  data;
      int  child[m];
 } treenode;
treenode tree[MAXSIZE];   /*樹孩子表示法的存儲數組*/
   int  root ;            /*根結點的下標*/      
   int  length;           /*樹中實際所含結點的個數*/
   char p[BMAXSIZE];      /*存放樹括號表示的數組*/
void bracktotree(char p[],int *root, int *length,treenode tree[])
{        /*將樹的括號表示法轉換成孩子表示法*/
  int stack[MAXSIZE];  /*存儲樹或子樹根結點的棧*/
  int top;             /*棧頂指針*/
  int i,j,k,l,done;    /*done為程序結束的標志*/
  k=0; j=0; *root=0;
  top=-1; done=1;      /*棧和標志的初始化*/
  tree[j].data=p[k];   /*產生孩子表示法中的根結點*/
  ++k;
  for (i=0;i<m;++i)
    tree[j].child[i]=-1;
  while (done)
   {
     if (p[k]=='(')    /*遇到左括號，則其前面的元素對應的結點進棧*/
        {  ++top;
           stack[top]=j;
           ++k;
          }
     else if (p[k]==')') /*遇到右括號，棧頂元素出棧*/
        { --top;
          if (top==-1)
            done=0;
          else ++k;
         }
         else if (p[k]==',')  
                 ++k;
               else  { /*將當前被掃描的元素作為棧頂元素的子女*/
                       ++j;
                       tree[j].data=p[k];
                       for (i=0;i<m;++i)
                         tree[j].child[i]=-1; 
                       l=stack[top];
                       i=0;
                       while (tree[l].child[i]!=-1)/*尋找棧頂元素的第一個空子女*/
                                ++i;
                       tree[l].child[i]=j;
                       ++k;
                      }
      }
    *length=j;  
  }
void preorder(treenode tree[],int root)
{  int i;
   if (root!=-1)
     {
       printf("%c",tree[root].data);
       for (i=0;i<m;++i)
          preorder(tree,tree[root].child[i]);
      }
 }
main()
{   
   printf("input the bracket:");
   scanf("%s",p);
   bracktotree(p,&root, &length,tree);
   preorder(tree,root);
}