중위 수식을 후위 수식으로 변환하는 프로그램

후위식 계산프로그램은 피연산자를 스택에 push하고 연산자를 만났을 때 pop하여 연산 후 다시 push하는 과정이었지만

중위수식을 후위식으로 변환하는 프로그램은 반대로 연산자를 push하고 피연산자는 그대로 출력합니다.

중위 수식을 후위 수식으로 변환할 떄 중요한 것은 연산자의 우선순위입니다.

괄호와 숫자로 구성된 중위 수식을 후위 수식으로 변환 할 때 연산자의 순위는 다음과 같습니다.

괄호 < +, - 연산자 < *, / 연산자

가장 중요한 것은 현재 처리중인 연산자와 스택에 있는 연산자의 우선순위를 이용한 처리 입니다.

1. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 낮을 때 

예를들어) 처리중인 연산자: + or - ,  스택에있는 연산자: * or / 일 때

=> 스택에 있는 연산자를 pop 해서 출력 후 처리 중인 연산자를 push 합니다.

2. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 클 때

예를들어) 처리중인 연산자: * or / , 스택에 있는 연산자: +, - 일 때

=> 현재 처리 중인 연산자를 그냥 push합니다.

3. 현재 처리중인 연산자의 우선순위와 스택에 있는 연산자의 우선순위가 같을 때

예를들어) 처리중인 연산자: +, 스택에 있는 연산자: - 일 때

=> 1번 경우와 똑같이 처리한다.

이유는 간단한 예시를 들면 쉽게 알 수 있습니다.

ex) 5-4+3일 때, 5/4*3 일 때 

=> 우선순위를 어떻게 하느냐에 따라 답이 달라집니다.

코드

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, char x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
char peek(stackType* s);
void infix_to_postfix(const char* s);
int prec(char op);
int main()
{
    
    infix_to_postfix("(2+3)*4+9");
    return 0;
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, char x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
char peek(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다.\n");
        exit(1);
    }
    return s->data[(s->top)];
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
void infix_to_postfix(const char* s)
{
    char ch,top_op;
    int n = strlen(s);
    stackType st;
    init(&st);
    for (int i = 0; i < n; i++)
    {
        ch = s[i];
        switch (ch)
        {
        case '+': case '-':case '*':case '/':
            while (!is_empty(&st) && (prec(ch) <= prec(peek(&st))))
            {
                printf("%c", pop(&st));
            }
            push(&st, ch);
            break;
        case '(':
            push(&st, ch);
            break;
        case ')':
            top_op = pop(&st);
            while (top_op != '(')
            {
                printf("%c", top_op);
                top_op = pop(&st);
            }
            break;
            //숫자일 떈 그대로 출력
        default:
            printf("%c", ch);
            break;
        }
    }
        //아직 스택에 남아있다면 다 뽑아냄
        while (!is_empty(&st))
            printf("%c", pop(&st));
    
}
int prec(char op)
{
    switch (op)
    {
    case '(':case ')': return 0;
    case '+':case '-': return 1;
    case '*':case '/':return 2;
    }
    return -1;
}
 

결과