중위 표기 수식을 전위 표기 수식으로 변환하는 프로그램

// 중위 표기 수식을 전위 표기 수식으로 변환하는 프로그램
 
#include <stdio.h>
#include <string.h>
 
#define MAX_STACK_SIZE 100
 
typedef int element;
 
typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;
 
// 스택 초기화 함수
void init(StackType *s) {
    s->top = -1;
}
 
// 공백 상태 검출 함수
int is_empty(StackType *s) {
    return (s->top == -1);
}
 
int is_full(StackType *s) {
    return (s->top == (MAX_STACK_SIZE - 1));
}
 
// 삽입 함수
void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->stack[++(s->top)] = item;
}
 
// 삭제 함수
element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[(s->top)--];
}
 
// 피크 함수
element peek(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[s->top];
}
 
// 연산자 우선순위를 반환한다.
int prec(char op) {
    switch (op) {
    case '(': case ')': return 0;
    case '+': case '-': return 1;
    case '*': case '/': return 2;
    }
    return -1;
}
 
// 매개변수로 전달된 수식문을 역순으로 변경해주는 함수 (스택 이용)
void reverse_exp(char *exp) {
    int i = 0, j = 0;
    int len = strlen(exp);
    char *a = (char *)malloc(sizeof(char)*(len + 1));
    StackType t;
 
    init(&t);   // 스택 초기화
                // 배열 exp에 들어있는 요소를 배열 a에 옮김.
    for (i = 0; i < len; i++) {
        a[i] = exp[i];
    }
    // 스택 t에 배열 a의 요소들을 push.
    for (i = 0; i < len; i++) {
        push(&t, a[i]);
    }
    // 배열 exp에 스택 t에 있는 요소들을 pop하여 나온 원소들을 삽입.
    for (i = 0; i < len; i++) {
        exp[i] = pop(&t);
    }
}
 
// 중위 표기 수식 -> 전위 표기 수식
char* infix_to_prefix(char exp[]) {
    int i = 0, j = 0;
    char ch, top_op;
    int len = strlen(exp);
    char *ex = (char *)malloc(sizeof(char)*(len + 1));
    StackType s;
    init(&s);            // 스택 초기화
    for (i = len - 1; i >= 0; i--) {
        ch = exp[i];
        switch (ch) {
        case '+': case '-': case '*': case '/': // 연산자
                                                // 스택에 있는 연산자의 우선순위가 더 크거나 같으면 출력                          
            while (!is_empty(&s) && (prec(ch) < prec(peek(&s)))) {
                ex[j++] = pop(&s);
            }
            push(&s, ch);
            break;
        case ')':        // 오른쪽 괄호
            push(&s, ch);
            break;
        case '(':        // 왼쪽 괄호
            top_op = pop(&s);
            // 오른쪽 괄호를 만날 때까지 출력
            while (top_op != ')') {
                ex[j++] = top_op;
                top_op = pop(&s);
            }
            break;
        default:
            ex[j++] = ch;
            break;
        }
    }
    while (!is_empty(&s)) {
        ex[j++] = pop(&s);
    }
    ex[j] = NULL;            // 문자열 끝은 널문자
 
    reverse_exp(ex);
    return ex;
}
 
void main() {
    printf("%s \n", infix_to_prefix("(2+3)*4+9"));
}