[자료구조] 원형 배열 큐를 이용해 전위식 계산하기 - C

큐를 이용한 예제로는 전위식 계산이 있다.

 

전위식은 주로 많이 사용하지 않지만, 큐를 이용한 예제로 한번씩 나온다.

 

전위식

연산자가 피연산자의 앞쪽에 위치한 식을 말한다.

ex) -+x9+28x+4863

 

 

전위식을 계산하는 데 우리는 원형 배열 큐를 사용하겠다.

 

기본적인 원형 배열 큐의 코드들을 먼저 구현하겠다.

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 10


char queue[MAX_SIZE];
int front = 1, rear = 1;

int isEmpty(){
    if(front==rear)
        return 1;
    return 0;
}

int isFull(){
    if(front==(rear+1)%MAX_SIZE)
        return 1;
    return 0;
}

void EnQueue(char data){
    if(isFull())
        exit(1);
    rear = (rear + 1) % MAX_SIZE;
    queue[rear] = data;
}

char DeQueue(){
    if(isEmpty())
        exit(1);
    front = (front + 1) % MAX_SIZE;
    return queue[front];
}

void ShowQueue(){
    if (isEmpty()) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue contents: ");
    int i = (front + 1) % MAX_SIZE;
    while (i != (rear + 1) % MAX_SIZE) {
        printf("%d ", queue[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

int main(void){
}

 

 

여기서 우리는 토큰을 이용하여 전위식을 하나하나 분석할 것이다.

• 토큰이 피연산자일 경우 : 큐에 삽입
• 토큰이 연산자일 경우 : 다음 토큰을 두개 더 뽑아와 두 개의 토큰이 모두 피연산자면 큐에 있던 연산자와 두 개의 피연산자를 사용하여 계산한 값을 큐에 삽입
• 두 개의 토큰이 모두 피연산자가 아닌 경우에는 토큰을 큐에 삽입

 

위 사진에서 우리는 토큰(f에서 나오는 것들) 이 연산자이다. 따라서 바로 EnQueue를 하여 rear 위치에 들어가게 된다.

 

 

 

위 사진에서 두번째 부분에, +라는 연산자가 나오고, 그 다음으로 두개를 뽑았을 때 2와 8이라는 피연산자가 나온다.

이런 경우에, 2와 8을 + 연산자를 통해 계산한 후에 그 값을 EnQueue하는 것이다.

따라서 rear에 2+8=10이 들어가게 된다.

 

정상적으로 쭉 실행이 완료되었다면 위처럼 하나의 값만이 남게된다.

 

이제 이 모든 과정을 코드로 구현해보겠다.

 

아래 코드에서는 총 3개의 함수를 추가로 구현하였다.

• isOperator : 연산자인지 확인하는 함수
• evaluate : 피연산자 두 개와 연산자 하나로 결과를 반환하는 함수
• prefix_eval : 전위식을 연산하는 함수

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

#define MAX_SIZE 20

int stack[MAX_SIZE];
int top = -1;

int isEmpty() {
    return top == -1;
}

int isFull() {
    return top == MAX_SIZE - 1;
}

void push(int data) {
    if (isFull()) {
        printf("Stack overflow!\n");
        exit(1);
    }
    stack[++top] = data;
}

int pop() {
    if (isEmpty()) {
        printf("Stack underflow!\n");
        exit(1);
    }
    return stack[top--];
}

void showStack() {
    if (isEmpty()) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack contents: ");
    for (int i = 0; i <= top; i++) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

int isOperator(char op) {
    return op == '+' || op == '-' || op == '*' || op == '/';
}

int evaluate(int op1, int op2, char operator) {
    switch (operator) {
        case '+': return op1 + op2;
        case '-': return op1 - op2;
        case '*': return op1 * op2;
        case '/': return op1 / op2;
        default: 
            printf("Invalid operator: %c\n", operator);
            exit(1);
    }
}

int prefix_eval(char arr[]) {
    int exp_len = strlen(arr);
    for (int i = exp_len - 1; i >= 0; i--) {
        if (isdigit(arr[i])) {
            push(arr[i] - '0');
        } else if (isOperator(arr[i])) {
            int op1 = pop();
            int op2 = pop();
            int result = evaluate(op1, op2, arr[i]);
            push(result);
        }
    }
    return pop();
}

int main(void) {
    char prefix[MAX_SIZE];
    printf("전위식을 입력하세요 : ");
    scanf("%s", prefix);
    int result = prefix_eval(prefix);
    printf("연산 결과 : %d\n", result);
    return 0;
}

 

 

실행 결과