데이터 구조 접미사 표현 식 을 접미사 표현 식 으로 바 꾸 고 값 을 구 합 니 다. pta 시험 문제, 소 백 심산 사.

데이터 구조 접미사 표현 식 을 접미사 표현 식 으로 변환 하고 값 을 구하 십시오.

1                  (100 )

제목 을 접미사 표현 식 으로 접미사 표현 식 출력 으로 바 꾸 고 접미사 표현 식 의 값 을 구하 십시오.간단 한 견 해 를 위해 우 리 는 약속 합 니 다. 1. 입력 한 접미사 표현 식 은 반드시 합 법 적 이 고 숫자, 네 가지 연산 자 +, -, *, / 와 소괄호 만 포함 합 니 다.2. 연산 수 는 모두 정수 (1 ～ 9) 이다.3. 입력 한 접미사 표현 식 은 20 자 를 초과 하지 않 습 니 다.4. 나눗셈 연산 의 결 과 는 여전히 정수 이다.
입력 형식: 입력 한 첫 줄 은 정수 N 으로 다음 N 줄 이 있 음 을 표시 합 니 다.줄 마다 접미사 표현 식 입 니 다.간단 한 견 해 를 위해 우 리 는 약속 합 니 다. 1. 입력 한 접미사 표현 식 은 반드시 합 법 적 이 고 숫자, 네 가지 연산 자 +, -, *, / 와 소괄호 만 포함 합 니 다.2. 연산 수 는 모두 정수 (1 ～ 9) 이다.3. 입력 한 접미사 표현 식 은 20 자 를 초과 하지 않 습 니 다.4. 나눗셈 연산 의 결 과 는 여전히 정수 이다.
출력 형식: 줄 마다 접미사 표현 식 에 대응 하 는 접미사 표현 식 을 출력 합 니 다. 빈 칸 을 사이 에 두 고 이 접미사 표현 식 을 출력 하여 계산 한 값 입 니 다.
샘플 입력: 여기에 입력 그룹 을 드 립 니 다.예 를 들 면:
6 2+4 3+27 2(4+6) (5/2+4)5+2 (3+5)(7-2)/4 5*(8-(3+2))
출력 사례: 여기에 해당 하 는 출력 을 드 립 니 다.예 를 들 면:
24+ 6 327*+ 17 246+* 20 52/4+5*2+ 32 35+72-4/ 10 5832± 15

// An highlighted block
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _nodechar
{
    char data;
    struct _nodechar *next;
} nodechar;

typedef struct _stackchar
{
    int size;
    nodechar *top;
} stackchar;

//  
stackchar *createStackchar(void);
//  
void pushchar(stackchar* pStack, char x);
//   #include 
void popchar(stackchar* pStack);
//      
char topchar(stackchar* pStack);
//  
bool emptychar(stackchar* pStack);
//  
void destroyStackchar(stackchar* pStack);

int getPriority(char op);

typedef struct _nodeint
{
    int data;
    struct _nodeint *next;
} nodeint;

typedef struct _stackint
{
    int size;
    nodeint *top;
} stackint;

//  
stackint *createStackint(void);
//  
void pushint(stackint* pStack, int x);
//  
void popint(stackint* pStack);
//      
int topint(stackint* pStack);
//  
bool emptyint(stackint* pStack);
//  
void destroyStackint(stackint* pStack);

int calucalte(int op1, char op, int op2);

int main(void)
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        char infix[21], postfix[21] = "\0";
        int index = 0;
        scanf("%s", infix);
        stackchar *pStackchar = createStackchar();
        for(int i = 0; infix[i] != '\0'; i++)
        {
            if(infix[i] >= '0' && infix[i] <= '9')
            {
                postfix[index++] = infix[i];
            }
            else if(infix[i] == '(')
            {
                pushchar(pStackchar, infix[i]);
            }
            else if(infix[i] == ')')
            {
                char c = topchar(pStackchar);
                popchar(pStackchar);
                while(c != '(')
                {
                    postfix[index++] = c;
                    c = topchar(pStackchar);
                    popchar(pStackchar);
                }
            }
            else
            {
                if(emptychar(pStackchar) || getPriority(infix[i]) >getPriority(topchar(pStackchar)))
                {
                    pushchar(pStackchar, infix[i]);
                }
                else
                {
                    while(!emptychar(pStackchar) && getPriority(infix[i]) <= getPriority(topchar(pStackchar)))
                    {
                        char c = topchar(pStackchar);
                        popchar(pStackchar);
                        postfix[index++] = c;
                    }
                    pushchar(pStackchar, infix[i]);
                }
            }
        }
        while(!emptychar(pStackchar))
        {
            char c = topchar(pStackchar);
            popchar(pStackchar);
            postfix[index++] = c;
        }
        printf("%s", postfix);
        destroyStackchar(pStackchar);
        stackint *pStackint = createStackint();
        for(int i = 0; postfix[i] != '\0'; i++)
        {
            if(postfix[i] >= '0' && postfix[i] <= '9')
            {
                int m = postfix[i] - '0';
                pushint(pStackint, m);
            }
            else
            {
                char op = postfix[i];
                int op2, op1;
                op2 = topint(pStackint);
                popint(pStackint);
                op1 = topint(pStackint);
                popint(pStackint);
                pushint(pStackint, calucalte(op1, op, op2));
            }
        }
        int answer = topint(pStackint);
        printf(" %d
", answer);
        popint(pStackint);
        destroyStackint(pStackint);
    }
    return 0;
}

int getPriority(char op)
{
    if(op == '+' || op =='-')
        return 1;
    if(op == '*' || op == '/')
        return 2;
    return 0;
}

int calucalte(int op1, char op, int op2)
{
    switch(op)
    {
    case '+':
        return op1 + op2;
        break;
    case '-':
        return op1 - op2;
        break;
    case '*':
        return op1 * op2;
        break;
    case '/':
        return op1 / op2;
        break;
    }
    return 0;
}
//  
stackchar *createStackchar(void)
{
    stackchar* p = (stackchar*)malloc(sizeof(stackchar));
    p->size = 0;
    p->top = NULL;
    return p;
}
//  
void pushchar(stackchar* pStack, char x)
{
    nodechar *t = (nodechar*)malloc(sizeof(nodechar));
    t->data = x;
    t->next = pStack->top;
    pStack->top = t;
    pStack->size++;
}
//  
void popchar(stackchar* pStack)
{
    nodechar *t = pStack->top;
    pStack->top = t->next;
    free(t);
    pStack->size--;
}
//      
char topchar(stackchar* pStack)
{
    return pStack->top->data;
}
//  
bool emptychar(stackchar* pStack)
{
    //return pStack->size == 0;
    return pStack->top == NULL;
}
//  
void destroyStackchar(stackchar* pStack)
{
    while (!emptychar(pStack))
    {
        popchar(pStack);
    }
    free(pStack);
}

stackint *createStackint(void)
{
    stackint* p = (stackint*)malloc(sizeof(stackint));
    p->size = 0;
    p->top = NULL;
    return p;
}
//  
void pushint(stackint* pStack, int x)
{
    nodeint *t = (nodeint*)malloc(sizeof(nodeint));
    t->data = x;
    t->next = pStack->top;
    pStack->top = t;
    pStack->size++;
}
//  
void popint(stackint* pStack)
{
    nodeint *t = pStack->top;
    pStack->top = t->next;
    free(t);
    pStack->size--;
}
//      
int topint(stackint* pStack)
{
    return pStack->top->data;
}
//  
bool emptyint(stackint* pStack)
{
    //return pStack->size == 0;
    return pStack->top == NULL;
}
//  
void destroyStackint(stackint* pStack)
{
    while (!emptyint(pStack))
    {
        popint(pStack);
    }
    free(pStack);
}