infix to prefix

#include <stdio.h>

#include <stdlib.h>

// 연산자 우선순위을 구하는 함수

// 곱셈과 나눗셈의 우선순위가 덧셈이나 뺄셈보다 더 높다.

int precedence(int op) {

    if(op=='(') return 0;

    if(op=='+'||op=='-') return 1;

    if(op=='*'||op=='/') return 2;

    return 3;

}

// 연산자 이외에는 괄호, 피연산자(숫자, 문자), 숫자, 문자 만 나오므로

// 숫자, 문자인지를 구하는 함수를 사용하면 된다.

int isnumber(int k) {

    if('a'<=k && k<='z') {

        return 1;

    }

    if('A'<=k && k<='Z') {

        return 1;

    }

    if('0'<=k && k<='9') {

        return 1;

    }

    return 0;

}

// 스택을 초기화 하는 것은 아주 간단하다.

// 스택의 top을 나타내는 0번째 원소에 0을 넣어 주기만 하면 된다.

void initstack(int s[]) {

    s[0]=0;

}

// push는 스택의 주소와 값을 인자로 가진다.

// 스택의 크기를 50으로 잡았으므로 49가 되면 full이 된다.

// top을 위한 공간을 한개 필요로 하므로, 실제로 스택을 위한 공간은

// 1이 줄어 들게 된다.

// 처음 스택에 push를 하는 경우를 생각해 보면 스택의 1번째 방에

// 값이 들어가야 한다는 것을 알수 있다.

// 따라서 먼저 스택의 0번째 원소를 증가시키고

// 스택의 top이 가리키는 장소에 값을 넣으면 된다.

void push(int s[], int v) {

    if(s[0]<49) s[++s[0]]=v;

    else {

        printf("스택이 꽉 찼습니다.");

        exit(1);

    }

}

// pop은 스택의 주소만 인자로 가진다.

// 스택의 top이 가리키는 방의 값이 반환된다.

// 그리고 스택의 top이 1이 줄게 된다.

// 스택의 top은 스택에 들어있는 원소의 갯수와도 같다.

int pop(int s[]) {

    if(s[0]>0) return s[s[0]--];

    printf("스택이 비었습니다.");

    exit(1);

}

// top 은 스택의 top이 가리키는 값을 반환한다.

int top(int s[]) {

    if(s[0]>0) return s[s[0]];

    printf("스택이 비었습니다.");

    exit(1);

}

// 스택이 empty인지는 top이 0인지를 검사하면 된다.

int isempty(int s[]) {

    return s[0]==0;

}

int main() {

    char infix[100];

    char prefix[100];

    // 스택의 top 을 가리키는 변수는 stack[0] 입니다.

    int stack[50]={0,};

    int stack1[50]={0,};

    int i, x, y;

    printf("중위 표기법: ");

    fflush(stdin);

    gets(infix);

    i=0;

    while(infix[i]!=0) {

        i+=1;

    }

    // 중위 표기를 뒤집어 준다.

    // revert infix notation;

    x=i;

    for(i=0;i<x/2;i+=1) {

        y=infix[i];

        infix[i]=infix[x-i-1];

        infix[x-i-1]=y;

    }

    // 왼괄호와 오른 괄호를 서로 바꾸어 준다.

    for(i=0;i<x;i+=1) {

        if(infix[i]=='(') {

            infix[i]=')';

        } else if(infix[i]==')') {

            infix[i]='(';

        }

    }

        

    i=0;

    while((x=infix[i])>0) {

        // 빈칸은 무시한다.

        if(x==' ') {

            

        // 왼괄호는 push한다.

        } else if(x=='(') {

            push(stack,x);

        // 오른괄호를 만나면 왼괄호까지를 모두 pop하면서 출력한다.[스택1에 push한다.]

        } else if(x==')') {

            while((y=pop(stack))!='(') {

                push(stack1, y);

            }

        // 숫자이면 출력한다. [스택1에 push한다.]

        } else if(isnumber(x)) {

          push(stack1, x);

        // 연산자이다. 

        // 스택의 연산자의 우선순위가 

        // 현재 연산자의 우선순위보다 같거나 높은 경우에는 

        // 모두 pop하여 출력한다.[스택1에 push한다.]

        // 그다음 push한다.

        } else { 

            while(!isempty(stack)&&precedence(top(stack))>=precedence(x)) {

                y=pop(stack);

                push(stack1, y);

            }

            push(stack, x);

        }

        i=i+1;

    }

    // 스택에 남아있는 연산자를 모두 pop하며 출력한다. [스택1에 push한다.]

    while(!isempty(stack)) {

        y=pop(stack);

        push(stack1, y);

    }

    // 스택1에 있는 원소들을 모두 pop하면서 출력한다.

    printf("\n전위 표기법: ");

    while(!isempty(stack1)) {

        y=pop(stack1);

        printf("%c ", y);

    }

    printf("\n");

    return 0;

}