스택을 활용한 계산기 만들기

중위 표기법

- 중위 표기법이란 일반적으로 사람이 수식을 표기할 때 사용하는 표기 방법

- 중위 표기법의 예시 : 7 * 5 + 3

 

후위 표기법

- 후위 표기법이란 컴퓨터가 계산하기에 편한 수식의 형태

- 후위 표기법에서 연산자는 뒤쪽에 위치

- 후위 표기법 예시 : 7 5 * 3 +

 

스택을 활용해 수식을 계산하는 방법

1. 수식을 후위 표기법으로 변환

2. 후위 표기법을 계산하여 결과를 도출

 

* 스택 구현하기

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

typedef struct Node { // 노드라는 구조체 정의
    char data[100]; // 하나의 문자열을 다룰수 있도록 함
    struct Node *next;
} Node;

typedef struct Stack {
    Node *top;
} Stack;

 

* 스택 함수 구현하기

void push(Stack *stack, char *data) {
    Node *node = (Node*)malloc(sizeof(Node));
    strcpy(node->data, data);
    node->next = stack->top;
    stack->top = node;
}

char* getTop(Stack *stack) {
    Node *top = stack->top;
    return top->data;
}

char* pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우 발생.\n");
        return NULL;
    }
    Node *node = stack->top;
    char *data = (char*)malloc(sizeof(char) * 100);
    strcpy(data, node->data);
    stack->top = node->next;
    free(node);
    return data;
}

 

중위 표기법을 후위 표기법으로 바꾸는 방법

- 피연산자가 들어오면 바로 출력

- 연산자가 들어오면 자기보다 운선순위가 높거나 같은 것들을 빼고 자신을 스택에 담음

- 여는 괄호 '('를 만나면 무조건 스택에 담음

- 닫는 괄호 ')'를 만나면 '('를 만날 때까지 스택에서 출력

 

* 우선순위 함수 만들기

int getPriority(char *i) {
    if (!strcmp(i, "(")) return 0;
    if (!strcmp(i, "+") || !strcmp(i, "-")) return 1;
    if (!strcmp(i, "*") || !strcmp(i, "/")) return 2;
    return 3;
}

 

* 변환 함수 만들기

// 나뉘어 들어오는 문자열들의 배열을 s라고 말함
char* transition(Stack *stack, char **s, int size) { // 들어오는 각 문자열의 갯수는 size
    char res[1000] = ""; // res 같은 경우는 후위 표기법으로 바뀐 결과가 담길 문자열
    for (int i = 0; i < size; i++) {
        
        // 해당 문자열이 연산자라면
        if (!strcmp(s[i], "+") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            
            // 자기보다 연산자 우선순위가 높은 것들을 다
            while (stack->top != NULL && getPriority(getTop(stack)) >= getPriority(s[i])) {
                
                // 스택에서 뽑은 뒤에
                strcat(res, pop(stack)); strcat(res, " ");
            }
            
            // 자신을 스택에 넣는것
            push(stack, s[i]);
        }
        // 기본 연산자가 아니라 여는 괄호라면 바로 스택에 넣을 수 있도록 하고
        else if (!strcmp(s[i], "(")) push(stack, s[i]);
        // 닫는 괄호인 경우 여는 괄호가 나올때까지 스택에서 뽑아서 바로 결과 배열에 담음
        else if (!strcmp(s[i], ")")) {
            while (strcmp(getTop(stack), "(")) {
                strcat(res, pop(stack)); strcat(res, " ");
            }
            // pop을 통해 여는 괄호도 나올수 있게 해줌
            pop(stack);
        }
        // 일반 숫자인 경우 바로 출력
        else {strcat(res, s[i]); strcat(res, " "); }
    }
    while (stack->top != NULL) {
        // 스택에 남아있는 원소가 있다면 다 꺼내주는게 기본적인 동작 과정
        strcat(res, pop(stack)); strcat(res, " ");
    }
    // result를 반환해서 후위 표기법을 뽑아낼 수 있음
    return res;
}

 

후위 표기법을 계산하는 방법

- 피연산자가 들어오면 스택에 담음

- 연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산한 뒤에 그 결과를 스택에 담음

- 연산을 마친 뒤에 스택에 남아있는 하나의 피연산자가 연산 수행 결과임

 

* 후위 표기법 계산

void calculate(Stack *stack, char **s, int size) {
    int x, y, z;
    for (int i = 0; i < size; i++) {
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            x = atoi(pop(stack));
            y = atoi(pop(stack));
            if (!strcmp(s[i], "+")) z = y + x;
            if (!strcmp(s[i], "-")) z = y - x;
            if (!strcmp(s[i], "*")) z = y * x;
            if (!strcmp(s[i], "/")) z = y / x;
            char buffer[100];
            sprintf(buffer, "%d", z);
            push(stack, buffer);
        }
        else {
            push(stack, s[i]);
        }
    }
    printf("%s\n", pop(stack));
}

 

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

typedef struct Node { // 노드라는 구조체 정의
    char data[100]; // 하나의 문자열을 다룰수 있도록 함
    struct Node *next;
} Node;

typedef struct Stack {
    Node *top;
} Stack;

void push(Stack *stack, char *data) {
    Node *node = (Node*)malloc(sizeof(Node));
    strcpy(node->data, data);
    node->next = stack->top;
    stack->top = node;
}

char* getTop(Stack *stack) {
    Node *top = stack->top;
    return top->data;
}

char* pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우 발생.\n");
        return NULL;
    }
    Node *node = stack->top;
    char *data = (char*)malloc(sizeof(char) * 100);
    strcpy(data, node->data);
    stack->top = node->next;
    free(node);
    return data;
}

int getPriority(char *i) {
    if (!strcmp(i, "(")) return 0;
    if (!strcmp(i, "+") || !strcmp(i, "-")) return 1;
    if (!strcmp(i, "*") || !strcmp(i, "/")) return 2;
    return 3;
}

// 나뉘어 들어오는 문자열들의 배열을 s라고 말함
char* transition(Stack *stack, char **s, int size) { // 들어오는 각 문자열의 갯수는 size
    char res[1000] = ""; // res 같은 경우는 후위 표기법으로 바뀐 결과가 담길 문자열
    for (int i = 0; i < size; i++) {
        
        // 해당 문자열이 연산자라면
        if (!strcmp(s[i], "+") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            
            // 자기보다 연산자 우선순위가 높은 것들을 다
            while (stack->top != NULL && getPriority(getTop(stack)) >= getPriority(s[i])) {
                
                // 스택에서 뽑은 뒤에
                strcat(res, pop(stack)); strcat(res, " ");
            }
            
            // 자신을 스택에 넣는것
            push(stack, s[i]);
        }
        // 기본 연산자가 아니라 여는 괄호라면 바로 스택에 넣을 수 있도록 하고
        else if (!strcmp(s[i], "(")) push(stack, s[i]);
        // 닫는 괄호인 경우 여는 괄호가 나올때까지 스택에서 뽑아서 바로 결과 배열에 담음
        else if (!strcmp(s[i], ")")) {
            while (strcmp(getTop(stack), "(")) {
                strcat(res, pop(stack)); strcat(res, " ");
            }
            // pop을 통해 여는 괄호도 나올수 있게 해줌
            pop(stack);
        }
        // 일반 숫자인 경우 바로 출력
        else {strcat(res, s[i]); strcat(res, " "); }
    }
    while (stack->top != NULL) {
        // 스택에 남아있는 원소가 있다면 다 꺼내주는게 기본적인 동작 과정
        strcat(res, pop(stack)); strcat(res, " ");
    }
    // result를 반환해서 후위 표기법을 뽑아낼 수 있음
    return res;
}

void calculate(Stack *stack, char **s, int size) {
    int x, y, z;
    for (int i = 0; i < size; i++) {
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            x = atoi(pop(stack));
            y = atoi(pop(stack));
            if (!strcmp(s[i], "+")) z = y + x;
            if (!strcmp(s[i], "-")) z = y - x;
            if (!strcmp(s[i], "*")) z = y * x;
            if (!strcmp(s[i], "/")) z = y / x;
            char buffer[100];
            sprintf(buffer, "%d", z);
            push(stack, buffer);
        }
        else {
            push(stack, s[i]);
        }
    }
    printf("%s\n", pop(stack));
}

int main(void) {
    Stack stack;
    stack.top = NULL;
    char a[100] = "( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";
    int size = 1;
    for (int i = 0; i < strlen(a); i++) {
        if (a[i] == ' ')  size ++;
        }
    char *ptr = strtok(a, " ");
    char **input = (char**)malloc(sizeof(char*) * size);
    for (int i = 0; i < size; i++) {
        input[i] = (char*)malloc(sizeof(char) * 100);
    }
    for (int i = 0; i < size; i++) {
        strcpy(input[i], ptr);
        ptr = strtok(NULL, " ");
    }
    char b[1000] = "";
    strcpy(b, transition(&stack, input, size));
    printf("후위 표기법: %s\n", b);
    size = 1;
    for (int i = 0; i < strlen(b) - 1; i++) { // 마지막은 항상 공백이 들어감으로 1을 빼기
        if (b[i] == ' ') size++;
        }
    char *ptr2 = strtok(b, " ");
    for (int i = 0; i < size; i++) {
        strcpy(input[i], ptr2);
        ptr2 = strtok(NULL, " ");
    }
    calculate(&stack, input, size);
    system("pause");
    return 0;
}