21. 후위 표기법 수식 계산 알고리즘

후위 표기법으로 된 수식을 계산하여 결괏값을 확인하는 알고리즘으로 Stack을 이용한다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define MAX_STACK_SIZE 100
typedef struct {
    int items[MAX_STACK_SIZE];
    int top;
} Stack;

// Stack 함수
void push(Stack  *s, char item){
    if(s->top >= MAX_STACK_SIZE - 1){
        printf("Stack Overflow\n");
        exit(1);
    }
    s->items[++(s->top)] = item;
}
int pop(Stack *s){
    if(s->top == -1){
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->items[(s->top)--];
}
int peek(Stack *s){
    if(s->top == -1){
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->items[(s->top)];
}
int is_empty(Stack *s){
    return (s->top <= -1);
}

// 후위 수식 계산 함수
int evaluate_postfix(char *postfix) {
    Stack s;
    s.top = -1;
    int i, op1, op2, result;
    char token;
    for (i = 0; postfix[i] != '\0'; i++) {
        token = postfix[i];
        if (isdigit(token)) {
            push(&s, token - '0'); // 문자를 숫자로 변환하여 스택에 push
        } else {
            op2 = pop(&s);
            op1 = pop(&s);
            switch (token) {
                case '+': result = op1 + op2; break;
                case '-': result = op1 - op2; break;
                case '*': result = op1 * op2; break;
                case '/': result = op1 / op2; break;
                case '%': result = op1 % op2; break;
                case '^': result = (int)pow(op1, op2); break;
                default:
                    printf("Invalid Expression: Unknown token '%c'\n", token);
                    exit(EXIT_FAILURE);
            }
            push(&s, result);
        }
    }
    result = pop(&s);
    if (!is_empty(&s)) {
        printf("Invalid Expression: Too many operands\n");
        exit(EXIT_FAILURE);
    }
    return result;
}

int main() {
    char postfix[MAX_STACK_SIZE];
    int result;
    printf("후위 수식 입력: ");
    fgets(postfix, MAX_STACK_SIZE, stdin);
    postfix[strlen(postfix) - 1] = '\0'; 
    result = evaluate_postfix(postfix);
    printf("결과 : %d\n", result);
    return 0;
}

 

Stack은 변환 알고리즘에서 사용했던 상태에서 item의 타입을 int로 변환했다.

evaluate_postfix() 함수는 후위 수식을 계산하는 함수이다. 만약 token이 피연산자라면 스택에 삽입한다. token이 연산자라면 스택에서 피연산자 2개를 삽입하여 해당 연산자를 이용하여 계산한다. 계산한 후 결과를 다시 스택에 삽입한다. 후위 수식 끝에 도달할 때까지 이를 반복한다.  반복이 종료되면 마지막으로 Pop 하여 최종 결과를 꺼내서 반환한다.