C언어 | 전위연산 알고리즘 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 200

typedef struct
{
    int stack[MAX_STACK_SIZE];
    int top;
} StackType;

void init(StackType *s)
{
    memset(s->stack, 0, sizeof(int) * MAX_STACK_SIZE);
    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, char item)
{
    if (is_full(s))
    {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else
        s->stack[++(s->top)] = item;
}

char pop(StackType *s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else
        return s->stack[(s->top)--];
}

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

int calculate(char op, int a, int b)
{
    if (op == '+')
        return a + b;
    else if (op == '-')
        return a - b;
    else if (op == '*')
        return a * b;
    else
        return a / b;
}

void prefix(StackType *s, char token)
{
    push(s, token);
    while (!is_operator(s->stack[s->top]) && !is_operator(s->stack[(s->top) - 1]) && is_operator(s->stack[(s->top) - 2]))
    {
        int b = pop(s);
        int a = pop(s);
        int op = pop(s);
        int value = calculate(op, a - '0', b - '0');
        push(s, value + '0');
    }
}

int main(void)
{
    StackType *s = (StackType*)malloc(sizeof(StackType));
    int n = 0;
    char token;

    FILE *fp = fopen("prefix.in", "r");
    FILE *fout = fopen("prefix.out", "w");

    fscanf(fp, "%d", &n);
    fprintf(fout, "%d\n", n);
    fgetc(fp);

    for (int i = 0; i < n; i++)
    {
        init(s);
        while (fscanf(fp, "%c", &token) != EOF)
        {
            prefix(s, token);
            if (fgetc(fp) == '\n')
                break;
        }
        fprintf(fout, "%c\n", s->stack[s->top]);
    }

    fclose(fp);
    fclose(fout);

    return 0;
}

 

코드 설명

 

// 헤더 (1~5)

scanf 오류 방지를 위해 _CRT_SECURE_NO_WARNINGS를 정의해주고, stdio.h, stdlib.h, string.h 라이브러리를 포함한다. 또한, MAX_STACK_SIZE를 200으로 정의한다.

 

// StackType 구조체 선언 (7~11)

StackType 구조체 안에는 stack 배열과 top이 있다. top은 제일 위에 있는 스택의 index값을 의미한다.

 

// init 함수 (13~17)

init 함수는 스택을 초기화하는 함수이다. memset 함수를 이용하여 스택을 모두 0으로 만들고, 스택 탑의 인덱스 top을 -1로 맞춘다.

 

// is_empty 함수 (19~22)

is_empty 함수는 스택을 인수로 받아 스택이 빈 상태를 반환하는 함수이다. top이 -1이면, 스택에 요소가 없는 빈 상태이다.

 

// is_full 함수 (24~27)

is_full 함수는 스택을 인수로 받아 포화상태의 스택을 반환하는 함수이다. top이 MAX_STACK_SIZE보다 하나 작은 값이면, 스택이 모두 다 찬 상태이다.

 

// push 함수 (29~38)

push 함수는 스택과 item을 인수로 받아, item을 스택에 쌓는 함수이다. 만약 스택이 포화상태가 아니라면, top보다 1만큼 큰 값을 인덱스로 가지는 스택에 item 값을 대입한다.

 

// pop 함수 (40~49)

pop 함수는 스택을 인수로 받아, 스택 제일 위에 있는 요소를 스택에서 빼는 함수이다. 만약 스택이 공백 상태가 아니라면, top보다 1만큼 작은 값을 인덱스로 가지는 스택의 요소를 반환한다.

 

// is_operator 함수 (51~54)

is_operator 함수는 op을 인수로 받아 연산자 +, -, *, / 를 반환하는 함수이다.

 

// calculate 함수 (56~66)

calculate 함수는 연산자 op, 피연산자 a, b를 인수로 받아, 연산자에 따라 계산한 값을 반환하는 함수이다.

 

// prefix 함수 (68~79)

prefix 함수는 스택과 token을 인수로 받아, 스택을 사용하여 전위 표기법 연산을 수행하는 함수이다. token을 먼저 스택에 push하고, 스택의 제일 위에 피연산자, 그 아래도 피연산자, 그 아래는 연산자이면, 그 세 개를 pop하여 calculate함수로 연산자에 따른 연산을 수행하고, 그 연산 된 값을 스택에 다시 push한다. 스택 제일 위에서부터 피연산자-피연산자-연산자 순으로 쌓여 있으면 이 과정을 반복한다.

 

// main 함수 ( 81~110)

스택 구조체 s, 총 전위 표기법 개수 n, token을 선언한다. 파일 포인터 *fp로 prefix.in파일을 열어 데이터를 읽고, *fout으로 prefix.out 파일을 열어 데이터를 쓴다. fscanf함수로 먼저 prefix.in 파일의 제일 첫 번째줄이 의미하는 총 전위 표기법의 개수를 읽고 이를 n에 대입한다. 그리고 그 n값을 prefix.out 제일 첫 번째줄에 출력한다. fscanf함수는 개행 문자를 못 읽으므로, fgetc 함수를 이용하여 prefix.in 파일의 개행 문자를 읽어 2번째 줄로 넘어간다. 그리고 n 값만큼 다음 과정을 반복한다. 먼저, init함수를 이용하여 스택을 초기화하고, fscanf함수를 이용하여 차례로 값을 token에 저장하여 prefix 연산을 수행한다. 만약 fgetc 함수가 개행 문자를 받으면, 다음 줄로 넘어가 다음 전위 표기법 식의 연산을 수행한다. 식의 연산을 다 수행하면 prefix 연산의 결과가 저장된 스택 제일 위의 값을 prefix.out 파일에 출력한다. n번의 수행이 끝났으면 prefix.in과 prefix.out 파일을 닫고 함수를 종료한다.