후위 표기식 계산 프로그램

- 수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)의 3가지 방법이 있음.

- 연산자가 피연산자 사이에 있으면 중위이고, 연산자가 피연산자 뒤에 있으면 후위이며, 연산자가 피연산자 앞에 있으면 전위라고 함.

- 인간은 주로 중위 표기법을 사용하지만 컴파일러는 주로 후위 표기법을 사용함.

- 후위 표기 수식은 괄호가 없어도 우선순위가 반영되어 있음.

// 후위 표기식 계산
 
#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element;
typedef struct {
    element stack[MAX_STACK_SIZE];
    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_STACK_SIZE - 1));
}
 
// 삽입 함수
void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->stack[++(s->top)] = item;
}
 
// 삭제 함수
element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[(s->top)--];
}
 
// 피크 함수
element peek(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[s->top];
}
 
// 후위 표기 수식 계산 함수
int eval(char exp[]) {
    int op1, op2, value, i = 0;
    int len = strlen(exp);
    char ch;
    StackType s;
    init(&s);
    for (i = 0; i < len; i++) {
        ch = exp[i];
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
            value = ch - '0';        // 입력이 피연산자이면 (실제 숫자로 바꿔주기 위해 필요)
            push(&s, value);
        }
        else {                            // 연산자이면 피연산자를 스택에서 제거
            op2 = pop(&s);
            op1 = pop(&s);
            switch (ch) {            // 연산을 수행하고 스택에 저장
            case '+': push(&s, op1 + op2); break;
            case '-': push(&s, op1 - op2); break;
            case '*': push(&s, op1 * op2); break;
            case '/': push(&s, op1 / op2); break;
            }
        }
    }
    return pop(&s);
}
 
void main() {
    int result;
    printf("후위표기식은 82/3-32*+\n");
    result = eval("82/3-32*+");
    printf("결과값은 %d\n", result);
}

내용 출처 : C언어로 쉽게 풀어 쓴 자료구조 (천인국 외 지음, 생능출판사)