나무의 괄호 표기 법

제목:
나무의 괄호 표기 법
시간:
1000 ms
메모리 제한:
3000 K
총 시간:
3000 ms
설명:
나무의 괄호 표시 법:
먼저 뿌리 결점 을 한 쌍 의 괄호 에 넣 은 다음 에 그 나 무 를 왼쪽 에서 오른쪽 순서 로 괄호 에 넣 고, 그 나 무 는 같은 방법 으로 처리한다. 같은 층 의 나무 와 그 뿌리 결점 은 둥 근 괄호 로 묶 고, 같은 층 의 나무 사 이 는 쉼표 로 막 고, 마지막 에는 닫 힌 괄호 로 묶는다.예 를 들 어 아래 그림 은 다음 과 같은 형식 으로 쓸 수 있다.
(a(b,c,d,e))
a
/ | | \
b c d e
다 진 트 리 의 괄호 표시 법 을 지정 합 니 다. 다 진 트 리 를 만 들 고 층 차 를 따라 출력 하 라 고 요구 합 니 다.
입력:
다 진 트 리 의 괄호 표시 법: 문자열
출력:
층 차 출력 다 진 트 리
입력 예시:
(a(b,c,d,e))
출력 예시:
abcde
사고방식: 입력 한 문자열 이 모두 몇 층 인지 먼저 판단 하고 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("
");

    //      ，   ，            
    for(i=0;i<levels;i++)
    {
        DestroyQueue(Q[i]);
    }
    return 0;
}