[4%] The following C program converts a preorder expression to its postorder form. For example, "+AB++ABC" is converted to "AB+AB+C+" with the program. Please fill in the missing parts of the program in C language.

#include<stdio.h>
#include<stdlib.h>

#define MAX_INPUT 100000

typedef struct _Stack_node{
    char val;
    struct _Stack_node *prev;
} Stack_node;

typedef struct _Stack{
    Stack_node *top;
} Stack;

Stack *new_stack(){
    Stack *stk = malloc(sizeof(Stack));
    stk->top = NULL;
    return stk;
}

char Stack_pop(Stack *stk){
    char value = stk->top->val;
    Stack_node *tmp = stk->top;
    /** TODO (A) **/
    free(tmp);
    return value;
}

void Stack_push(Stack *stk, char value){
    Stack_node *new_node = malloc(sizeof(Stack_node));
    new_node->val = value;
    /** TODO (B) **/
    stk->top = new_node;
    return;
}

int Stack_is_empty(Stack *stk){
    return stk->top == NULL;
}

void pre_to_post(char *);
void post_to_pre(char *);

int main(){
    char input[MAX_INPUT];
    scanf("%s", input);
    pre_to_post(input);
    return 0;
}

void pre_to_post(char *input){
    Stack *stk = new_stack();
    for (int i = 0; input[i] != '\0'; ++i){
        switch(input[i]){
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '%':
                Stack_push(stk, input[i]);
                break;
            default:
                printf("%c", input[i]);
                while (!Stack_is_empty(stk) && stk->top->val == 'A'){
                    char top = Stack_pop(stk);
                    printf("%c", Stack_pop(stk));
                }
                if (!Stack_is_empty(stk)) Stack_push(stk, 'A');
        }
    }
    printf("\n");
}