[Data Structure] #2-5 스택을 이용한 후기 표기법 계산

스택을 이용한 후기 표기법 계산

 오늘 포스트는 스택을 활용한 후기표기법 계산이다. 후위 표기법의 계산 방식은 아주 단순하다. 잘못된 입력값이 들어오지 않는다고 가정했을 때, 피연산자가 들어오면 스택에 쌓고 연산자(+,-,*,/)가 들어오면 스택에서 피연산자 2개를 꺼내서 계산한 후에 다시 넣어주면 된다. 

 참고로 나는 C언어를 할 줄 모른다. 그런데 C로 자료구조를 배우다 보니 C 언어를 조금씩 배우는 기분이다. 오늘 몰랐던 점은 String과 같은 char[]을 인자로 받아서.. 그 길이를 계산하기 위해서 string.h의 strlen()을 이용해 len을 계산한다는 점이다. C언어를 할 줄 아시는 분은 아주 쉬운 것이었겠지만 나는 여태껏 무조건 길이를 함께 넘겨줘야 하는줄 알았다.. ㅜㅜ; 

잡소리를 여기까지 하고 책에서 설명해준 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE_STACK 100

#define FALSE 0
#define TRUE 1

// 수식을 표기하는 방법에는 중위(infix), 전위(prefix), 후위(postfix) 방식이 존재
// 연산자(+,-,*,/)가 피연산자(numbers)보다 중간에 있으면 중위, 앞에 있으면 전위, 뒤에 있으면 후위다
// 컴퓨터 컴파일러는 후위 표기 선호한다. 왜냐하면
// 후위 표기법은 1. 괄호가 없어도 우선순위를 알 수 있고, 2. 수식을 끝까지 읽을 필요가 없기 때문
// 여기서는 매개변수 exp가 후위 표기법으로 들어온다고 가정함

typedef int element;
typedef struct {
    element stack[MAX_SIZE_STACK];
    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_SIZE_STACK -1;
}

void push(StackType *s, element item){
    if (is_full(s))
        exit(1);
    s->stack[++(s->top)] = item;
}

element pop(StackType *s){
    if (is_empty(s))
        exit(1);
    return s->stack[(s->top)--];
}

element peek(StackType *s){
    if (is_empty(s))
        exit(1);
    return s->stack[s->top];
}

// exp[] 는 후위 표기법으로 된 수식
int eval(char exp[]){
    int op1, op2, value, i;
    int len = (int) strlen(exp);
    char ch;
    StackType s;
    init(&s);
    for (i=0; i<len; i++) {
        ch = exp[i];
        
        // ch가 피연산자일 경우. char형태의 값으로 들어오기 때문에 char '0' = 48을 가짐.
        // 실제 숫자값으로 변경하기 위해 - '0'을 해준다.
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
            value = ch - '0';
            push(&s, value);
            continue;
        }
        
        op1 = pop(&s);
        op2 = pop(&s);
        
        switch (ch) {
            case '+': value = op1 + op2; break;
            case '-': value = op1 - op2; break;
            case '*': value = op1 * op2; break;
            case '/': value = op1 / op2; break;
            default: exit(1); break;
        }
        push(&s, value);
    }
    return pop(&s);
}

int main(){
    int result;
    char *postfix = "82/3-32*+";
    result = eval(postfix);
    printf("후위 표기식 %s의 계산 결과 : %d\n",postfix,result);
    return 0;
}

군더더기 없이 깔끔하고 아주 쉬워서 더 이상의 자세한 설명은 생략한다!!