표현식 트리 생성 및 출력

표현식 트리 생성 및 출력
프로그램을 만들어서 먼저 문자열을 훑어보고 이 문자열에 따라 두 갈래 트리 (지침으로 저장) 를 만듭니다. 주의해야 할 것은 이 트리가 반드시 표현식 트리일 것입니다. (교재 5.25.8 참조)예를 들어 다음 순서대로 문자열을 반복합니다.

13 ###*5##9## 연산자는 100보다 작은 값을 더하기 곱하기만 할 수 있으며 각 결점은 공백으로 구분됩니다. 여기서 "#"은 빈 트리를 나타냅니다

이 두 갈래 나무를 세운 후에 요구에 따라 두 갈래 나무를 출력합니다.
입력
입력은 여러 그룹의 테스트 데이터로 구성되어 있다.
각 그룹의 데이터는 표현식 트리의 선행 반복 시퀀스를 포함하고 문자열의 길이는 0보다 크며 100을 넘지 않습니다.
출력
각 그룹의 데이터에 대해 한 줄을 출력합니다. 내용은 이 표현식 트리의 괄호 표현식입니다. 예시를 보십시오.
샘플 입력

13 # # * 5 # # 9 # #

13 # # 5 # # 9 # #

샘플 출력(13+(5*9)(13+5)*9)

#include 
#include 
#include 

typedef struct BiNode
{
    char data[5];
    struct BiNode *lchild,*rchild;
}BiNode,*Bitree;
int m = 0;
Bitree G;
char b[101][5];

Bitree CreateBItree( Bitree G ) // 
{
    if( b[m][0] == '#' ) { G = NULL; m++; }
    else
    {
        G = (Bitree)malloc(sizeof(struct BiNode));
        strcpy( G->data , b[m++] );
        G->lchild = CreateBItree( G->lchild );
        G->rchild = CreateBItree( G->rchild );
    }
    return G;
}

void INorder( Bitree G  )
{
    if( G != NULL )
    {
        if( G->data[0] == '+' || G->data[0] == '-' || G->data[0] == '*' || G->data[0] == '/' )
        {
            printf("(");
            INorder( G->lchild  );
            printf("%s",G->data);
            INorder( G->rchild  );
            printf(")");
        }
        else printf("%s",G->data);
    }

}

int main()
{
    char a[1000];
    while( gets( a ) != NULL )
    {
        int p = 0 , i, q = 0;
        for( i = 0; a[i] != '\0'; i++ )
        {
            if( a[i] != ' ' )
                b[p][q++] = a[i];
            else
            {
                b[p++][q++] = '\0';
                q = 0;
            }
        }
        b[p++][q++] = '\0';   // 

        G = CreateBItree(  G );  // ， ；
        INorder( G  );
        printf("
");
        m = 0;
    }
    return 0;
}

최종 결과를 출력하려면: (13+(5*9) = 58 (13+5)*9) = 162 함수 하나만 추가하면 함수 코드는 다음과 같습니다.

int make_end( Bitree G ) // 
{
    if( G != NULL )
    {
        if( G->data[0] == '+' || G->data[0] == '-' || G->data[0] == '*' || G->data[0] == '/' )
        {
            switch ( G->data[0] )
            {
                case '+':return make_end( G->lchild ) + make_end( G->rchild );break;
                case '-':return make_end( G->lchild ) - make_end( G->rchild );break;
                case '*':return make_end( G->lchild ) * make_end( G->rchild );break;
                case '/':return make_end( G->lchild ) / make_end( G->rchild );break;
            }
        }
        else
        {
            char f[100];   int x , y ;
            strcpy( f , G->data );
            for( x = 0 , y = 0; f[x] != '\0'; x++ )
            {
                y = y * 10 + f[x] - '0';
            }
            return y;
        }
    }
}