연습 문제 3.11 표현 식 변환 (25 점)

산술 표현 식 은 접두사 표현법, 접두사 표현법 과 접두사 표현법 등 형식 이 있다.일상적으로 사용 하 는 산술 표현 식 은 두 개의 연산 수 중간 에 있 는 접두사 표현법, 즉 이원 연산 자 를 사용한다.디자인 프로그램 에서 접미사 표현 식 을 접미사 표현 식 으로 변환 하 십시오.
입력 형식:
한 줄 에 빈 칸 이 없 는 접두사 표현 식 을 입력 하 십시오.
출력 형식:
한 줄 에서 변 환 된 접미사 표현 식 을 출력 하려 면 서로 다른 대상 (연산 수, 연산 기호) 사이 에 빈 칸 으로 구분 해 야 하지만 끝 에 빈 칸 이 있어 서 는 안 됩 니 다.
입력 예시:

2+3*(7-4)+8/4

출력 예시:

2 3 7 4 - * + 8 4 / +

#include
#include
#include
 
#define ERROR - 1
#define MAXLENTH 100
#define maxsize 20
typedef char ElementType;
 
typedef struct snode* PtrToSnode;
struct snode
{
    ElementType data;
    PtrToSnode next;    
};
 
typedef PtrToSnode mystack;
 
bool isEmpty(mystack ms);
mystack create();
bool pushdata(mystack ms, ElementType X);
ElementType popdata(mystack ms);
 
int OprToDig(char ch);
 
int OprToDig(char ch)
{
    int val;
    switch (ch)
    {
        case '+':
            val = 1;
            break;
        case '-':
            val = 1;
            break;
        case '*':
            val = 2;
            break;
        case '/':
            val = 2;
            break;
        case '(':
            val = 0;
            break;
        case ')':
            val = 0;
            break;
        default:
            printf("%c is invalid Charn", ch);
            break;
    }
    return val;
}
 
mystack create()
{
    mystack ms = (mystack)malloc(sizeof(struct snode));
    ms->next = NULL;
    return ms;
        
}
 
bool isEmpty(mystack ms)
{
    return (ms->next == NULL);
}
 
bool isFull(mystack ms)
{
    return (ms->next == maxsize - 1);
}
 
bool pushdata(mystack ms,ElementType x)
{
    bool rlt = false;
    PtrToSnode tmpcell = (PtrToSnode)malloc(sizeof(struct snode));
    tmpcell->data = x;
    tmpcell->next = ms->next;
    ms->next = tmpcell;
    rlt = true;
    return rlt;
}
 
ElementType popdata(mystack ms)
{
    if(isEmpty(ms))
    {
        printf("empty stcak.");
        return ERROR;
    }
    else
    {
        ElementType rlt = ms->next->data;
        PtrToSnode tmpcell;
        tmpcell = ms->next;
        ms->next = tmpcell->next;
        free(tmpcell);
        return rlt;
    }
}
 
int main()
{
    bool flag = false;
    bool isFirst = true;
    mystack stk = create();
    char exrn[MAXLENTH];
    gets(exrn);
    
    int i = 0;
    while(exrn[i]!='\0')
    {
        if(((i==0) && (exrn[i]=='-'||exrn[i]=='+')) || ((exrn[i]>='0' && exrn[i]<='9')||exrn[i]=='.') || ((exrn[i]=='-'||exrn[i]=='+')&&exrn[i-1]=='('))
        {
            if(flag && !isFirst)
            {
                printf(" ");
                flag = false;
            }
                isFirst = false;
            if(exrn[i] == '+')
            {
                i++;
            }
            printf("%c", exrn[i]);
            i++;
            while((exrn[i]>='0' && exrn[i] <= '9')|| exrn[i] == '.')
            {
                printf("%c",exrn[i++]);
            }
            continue;
        }
        else
        {
            flag = true;
            if(exrn[i] == '(')
            {
                pushdata(stk,exrn[i]);
            }
            else if(exrn[i] == ')')
            {
                ElementType ch;
                while((ch = popdata(stk))!='(')
                {
                    printf(" %c",ch);
                }
            }
            else
            {
                if(isEmpty(stk))
                {
                    pushdata(stk,exrn[i]);
                }
            
                else
                {
                    if( OprToDig(exrn[i]) > OprToDig(stk->next->data))
                    {
                        pushdata(stk,exrn[i]);
                    }
                    else if(OprToDig(exrn[i]) <= OprToDig(stk->next->data))
                    {
                        do
                        {
                            printf(" %c", popdata(stk));
                        }
                        while( (stk->next!=NULL)&&(OprToDig(exrn[i]) <= OprToDig(stk->next->data)) );
                        pushdata(stk,exrn[i]);
                    }
                }
                
            }
        }
        i++;
 
    }
    while(!isEmpty(stk))
    {
        printf(" %c", popdata(stk));
    }
    
    system("pause");
    
}