후위표기식 전환 (스택) 2

Postfix2

이전 포스트에선 postfix로 변환되어있는 수식을 계산하는 코드를 작성하였는데, 이번 포스트에선 infix로 표현된 수식을 postfix로 변환하는 소스코드를 작성하고자 한다.

Condition

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

Boj-1918

IDEA

• 문자열을 입력받아 앞에서부터 읽고 연산자는 스택에 넣은 후 뒤로 보낸다.
• 피연산자는 뒤로 보내지 않고 바로 출력한다.
• 괄호가 있다면 괄호도 연산자로 취급한다.
• 여는 괄호는 연산자 우선순위가 가장 낮다.
• 닫는 괄호를 만나게 된다면 스택에 들어있는 연산자를 '(' 연산자가 나올 때까지 POP 한다.

CODE

전체 소스코드 위치

• 스택의 ADT를 모두 구현하였음
• void init(StackType* s); // 스택을 초기화하는 함수 int is_full(StackType* s); // 스택이 가득 찼는지 확인하는 함수. int is_empty(StackType* s); // 스택이 비어있는지 확인하는 ㅎ마수 void push (StackType* s, element* item); //스택에 값을 집어넣는 함수 element pop(StackType* s); // 스택의 가장 마지막에 들어온 값을 반환 및 삭제 int priority(char* ch); //연산자 우선순위를 판별하여 크기로 리턴함 void calculate(StackType* s, char* infix); // idea 내용 구현 함수
• calculate 함수

void calculate(StackType* s, char* infix) {    //infix : 입력값
    char *c;

    for (int i = 0; i < strlen(infix); i++) {
        switch (infix[i]) {
        case '+': case '-': case '*': case '/':    //연산자라면 우선순위가 높은것을 먼저~

            while (!is_empty(&(*s)) && priority(&infix[i]) <= priority(&(s->data[s->top]))) {
                printf("%c", pop(&(*s)));
            }
            push(&(*s), &infix[i]);
            break;

        case '(':    // 여는 괄호가 나오면 무조건 스택에 push한다.
            push(&(*s), &infix[i]);
            break;

        case ')':    // 닫는 괄호가 나오면 여는 괄호가 나올때까지 pop 한다.
            c = &(s->data[s->top]);
            while (*c != *"(") {
                printf("%c", pop(&(*s)));
                c = &(s->data[s->top]);
            }
            pop(&(*s));
            break;

        default:    // 피연산자의 경우 바로 출력한다.
            printf("%c", infix[i]);
            break;
        }
    }

    while (s->top != -1) {    //언제까지? 스택이 빌 때까지
        printf("%c", pop(&(*s)));
    }
}

• priority 함수

int priority(char* ch) {
    switch (*ch)
    {
    case '*':    //곱하기와 나누기 연산자 순위가 가장 높고
    case '/':
        return 2;

    case '+':
    case '-':
        return 1;

    default:    // 피연산자와 괄호의 우선순위가 가장 낮다.
        return -1;
    }
}

전체 소스코드는 github에 첨부하였고, raw 코드를 링크하였다.