스택의 응용(후위 표기법)

저희(사람)이 사용하는 수식은 중위표기법인데요. 하지만 컴퓨터가 수식을 계산할 때에는 후위표기식으로 바꾸어서 계산합니다. 예를 들어 8/2-3+3*2을 계산한다고 하면 컴퓨터는 82/3-32*+로 바꾸어서 계산해요.(수식에 사용되는 숫자는 한자리라고 가정)

중위 수식을->후위 수식으로 바꾸는게 후위표기식을 계산하는 것보다 어렵기에.. 먼저 후위표기식을 계산하는 것부터 시작할게요. 알고리즘은 다음과 같아요.

*문자열을 읽는다고 가정

-숫자라면 스택에 집어넣습니다.

-연산자가 나오면 스택에서 숫자를 2개 꺼내서 연산후에 다시 스택에 집어넣습니다.

-문자열이 끝났다면 스택에 남아있는 값이 결과값.

다음의 stack.h/stack.c를 사용했습니다.

#ifndef STACK_H
#define STACK_H
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef int element;
typedef struct stack {
    element data;
    struct stack *next;
}Stack;
typedef struct stackList {
    Stack *top;
}sList;
 
void initStack(sList*);
void push(sList*, element);
void pop(sList*);
bool isEmpty(sList*);
int peek(sList*);
void freeStack(sList*);
 
#endif // !STACK_H

#include "stack.h"
 
void initStack(sList *list) {
    list->top = NULL;
}
void push(sList *list, element data) {
    Stack *new = (Stack*)malloc(sizeof(Stack));
    new->data = data;
    new->next = list->top;
    list->top = new;
}
void pop(sList *list) {
    Stack *temp = list->top->next;
    free(list->top);
    list->top = temp;
}
bool isEmpty(sList *list) {
    if (list->top == NULL) return true;
    else return false;
}
int peek(sList *list) {
    if (isEmpty(list)) return 0;
    else return list->top->data;
}
void freeStack(sList *list) {
    while (!isEmpty(list)) {
        pop(list);
    }
}

후위표기식의 계산

int eval(char* exp) {
    sList s;
    initStack(&s);
    while (*exp) {
        if (*exp == '+' || *exp == '-' || *exp == '*' || *exp == '/') {
            //연산자일 경우에 스택에서 숫자를 2개 꺼내서 계산해요
            int x, y;//스택에서 꺼내서 계산할때 순서 주의!!!
            y = peek(&s); pop(&s);//먼저 꺼낸것이 뒤
            x = peek(&s); pop(&s);//다음 꺼낸것이 앞
            switch (*exp) {
            case '+':
                push(&s, x + y);
                break;
            case '-':
                push(&s, x - y);
                break;
            case '*':
                push(&s, x * y);
                break;
            case '/':
                push(&s, x / y);
                break;
            }
        }
        else {//숫자일 경우 스택에 넣어요
            push(&s, *exp - '0');
        }
        exp++;
    }
    return peek(&s);//결과값을 리턴해요
}

main함수는 적지 않았지만 eval("82/3-32*+"); 을 호출하면 결과값인 7이 나옵니다.

다음으로 중위 표기식을 -> 후위표기식으로 바꾸는 작업을 해볼게요. 알고리즘은 다음과 같아요.

*연산자의 가중치는 다음과 같습니다.

 1순위 : * , /

 2순위 : + , -

 3순위 : (

-숫자는 바로 출력합니다.

-연산자는 스택에 넣습니다.

-스택의 맨위에 있는 연선자가 현재 연산자보다 가중치가 높거나 같다면 출력합니다.

-그렇지 않다면 스택에 넣습니다.

- '(' 는 무조건 스택에 넣습니다.

- ')' 를 만나면 '('를 만날 때까지 스택에 있는 연산자들을 출력합니다. 후에 '(' 를 꺼냅니다.

중위표기식->후위표기식

int getWeight(char k) {
    switch (k)
    {
    case '*':
    case '/':
        return 1;
    case '+':
    case '-':
        return 0;
    case '(':
        return -1;
    }
}

void change(char* buf, char *exp) {//exp->buf로 변환
    sList stack1; initStack(&stack1);//스택 초기화
    int k = 0;
    for (int i = 0; exp[i]; i++) {
        if ('0' <= exp[i] && exp[i] <= '9') {
            buf[k++] = exp[i];//숫자라면 바로저장해요
        }
        else if (isEmpty(&stack1) || exp[i] == '(') {
            push(&stack1, exp[i]);//비었거나 '('라면 무조건 스택에 넣어요
        }
        else if (exp[i] == ')') {//닫는 괄호면
            while (peek(&stack1) != '(') {//여는 괄호가 나올 때까지
                buf[k++] = peek(&stack1); //문자열에 저장 후
                pop(&stack1);              //pop해요
            }
            pop(&stack1);//여는 괄호를 제거해요
        }
        else {//연산자일 경우에
            if (getWeight(peek(&stack1)) < getWeight(exp[i])) {
                push(&stack1, exp[i]);//현재 연산자가 스택의 맨위에 있는
                //연산자보다 우선순위가 높으면 그냥 스택에 넣어요
            }
            else {//현재 연산자와 스택의 맨위에 있는 연산자의 가중치를 비교해서
                while (!isEmpty(&stack1) && getWeight(peek(&stack1)) >= getWeight(exp[i])) {
                    //비거나 가중치가 작은 연산자를 만날때까지
                    buf[k++] = peek(&stack1);//스택에서 꺼내요
                    pop(&stack1);
                }
                push(&stack1, exp[i]);//후에 스택에 삽입
            }
        }
    }
    while (!isEmpty(&stack1)) {//문자열이 다 끝났다면
        buf[k++] = peek(&stack1);//빌때까지 스택에서 꺼내요
        pop(&stack1);
    }
    buf[k] = '\0';//*문자열의 마감처리
}

저는 후위식으로 바꿀때 출력하는 형식이 아닌, 문자열로 저장해서 출력하는 형식으로 코딩했어요. 이유는 위의 후위식을 계산하는 함수를 이용하기 위해서이죠!

간단한 결과:

int main(void) {
    char exp[] = "8/2-3+3*2"; //8/2-3+3*2계산
    char buf[64];
    change(buf, exp);//buf에 exp의 후위식 저장
    printf("%s = ", buf);
    printf("%d\n", eval(buf));
    return 0;
}

출력창:

깔끔하게 출력되네요!