树的括号表示法_树中对于括号字符串怎么看

思路：先判断输入的字符串一共有几层，如有levels层则动态初始化levels个队列。

再从第一个字符开始判断字符串中的当前字符串是属于哪一层的，若属于第i层，则插入到第i层的队列当中。

最后，依次将第1层到第levels层队列中的元素出队并输出，则完成层序输出。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElemType;
/队列相关/
typedef struct _QNode
{
    ElemType key;
    struct _QNode *next;
}QNode;
 
typedef struct _Queue
{
    QNode *front;
    QNode *rear;
}Queue;
 
void InitQueue(Queue &Q)
{
    Q.front=NULL;
    Q.rear=NULL;
}//InitQueue
 
bool isEmpty(Queue &Q)
{
    if(Q.front==NULL)
    return true;
    return false;
}//isEmpty
 
void EnQueue(Queue &Q, ElemType e)
{
    QNode *s=(QNode*)malloc(sizeof(QNode));
    s->key=e;
    s->next=NULL;
    if(isEmpty(Q))
    {
        Q.front=s;
        Q.rear=s;
        return;
    }
    else
    {
        Q.rear->next=s;
        Q.rear=s;
    }
}//EnQueue
 
bool DeQueue(Queue &Q,ElemType &e)
{
    if(isEmpty(Q))
    return false;
    else
    {
        QNode *node=Q.front;
        e=node->key;
        Q.front=Q.front->next;
        if(Q.front==NULL)
        {
            Q.rear=NULL;
        }
        free(node);
    }
    return true;
}//DeQueue
 
void DestroyQueue(Queue &Q)
{
    ElemType temp;
    while(DeQueue(Q,temp)){}
}//DestroyQueue
 
 
//判断输入的字符串共有几层
int Levels(char *&str)
{
    int levels=0,i;
    for(i=0;i<strlen(str);i++)
    {
        if(str[i]=='(')
           levels++;
    }
    return levels;
}
 
//判断当前的字符e属于哪一层
int Inlevel(char *&str,ElemType e)
{
    int i=0,left=0,right=0;
    ElemType c;
    c=str[0];
    while(c!=e)
    {
        c=str[i];
        i++;
        if(c=='(') left++;
        if(c==')') right++;
     }
     return left-right;
}
 
int main()
{
    char *str=(char*)malloc(sizeof(char));
    scanf("%s",str);
    int levels=Levels(str);
    //动态分配levels个队列
    Queue *Q=(Queue*)malloc(sizeof(Queue)*levels);
    int i;
    for(i=0;i<levels;i++)
    {
        InitQueue(Q[i]);
    }
    for(i=0;i<strlen(str);i++)
    {
        if(str[i]!=','&&str[i]!='('&&str[i]!=')')
        {
            //当前字符属于哪个队列，就插入到哪个队列后面
            EnQueue(Q[Inlevel(str,str[i])-1],str[i]);
        }
    }
 
    //从第一层的队列依次出队并输出，即为层序输出
    for(i=0;i<levels;i++)
    {
        ElemType temp;
        while(!isEmpty(Q[i]))
        {
            DeQueue(Q[i],temp);
            printf("%c",temp);
        }
    }
    printf("\n");
 
    //销毁所有队列，可没有，但为了程序的健壮性最好有
    for(i=0;i<levels;i++)
    {
        DestroyQueue(Q[i]);
    }
    return 0;
}