5. 스택을 활용한 계산기 만들기 - 중위표기법 / 후위표기법 / 스택 구현 / 우선순위 함수 만들기 - 후위 표기법으로 변환 / 후위 표기법 계산 하기 / 만든 계산기 사용하기 / strcmp, strcat함수 추가..

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

스택을 활용해 계산기를 만들어 본다. 

 

중위 표기법

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

중위 표기법의 예시 : 7 * 5 + 3 (2개의 피연산자 사이에 연산자가 들어간다.)

 

후위 표기법

후위 표기법이란 컴퓨터가 계산하기에 편한 수식의 형태이다. 후위 표기법에서 연산자는 뒤쪽에 위치한다.

후위 표기법의 예시 : 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;

먼저, Node와 스택을 정의한다. Node에는 하나의 문자열을 담도록 만들 것인데, 숫자는 길이가 길어질 수 있으므로 문자열로 처리하기 위함이다.

 

스택 구현하기 - 스택함수 구현하기

스택을 구현하기 위해 쓰일(필요한) 함수를 먼저 정의 한다.

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){ //최상단 노드인 "Top"을 반환하는 함수
    Node *top = stack->top;
    return top->data;
}

char* pop(Stack *stack){ //스택 추출 함수(top을 스택에서 추출, 반환함)
    if (stack->top == NULL){
        printf("스택 언더플로우가 발생했습니다\n");
        return 0;
    }
    Node *node = stack->top;
    char *data = (char*)malloc(sizeof(char)*100);
    strcpy(data, node->data);
    stack->top = node->next;
    free(node);
    return data;
}

 

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

1. 피연산자가 들어오면 바로 출력한다
2. 연산자가 들어오면 자기보다 우선순위가 높거나 같은 것들을 빼고 자신을 스택에 담는다
3. 여는 괄호'('를 만나면 무조건 스택에 담는다.
4. 닫는괄호')'를 만나면 '('를 만날 때 까지 스택에서 출력한다.

후위 표기법으로 변환 - 우선순위 함수 만들기

후위 표기법으로 변환하기 위해, 들어온 숫자(피연산자) 및 연산자의 우선순위를 "숫자"로 알려주는 함수를 먼저 만든다.

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;
}

숫자가 클수록 우선순위가 높은 것으로 가정하고 정의하였다. 일반 숫자(피연산자)인 경우 가장 큰 우선순위를 갖는다. 이전 C_basic 학습 시, <string.h>에 포함 된 문자열 처리 함수 중, strcmp()함수에 대한 추가 설명 및 학습이 필요하여, 다음과 같은 내용을 덧붙인다.

+ strcmp()함수에 대한 추가 설명
매개변수로 들어온 두개의 문자열을 비교 하여 문자열이 완전히 같다면 0을 반환하고, 다르면 음수 혹은 양수를 반환하는 함수입니다.
여기서 -1, 1은 매개변수로 들어온 문자열들을 비교하다가 다른 문자가 나왔을때 그 문자의 아스키 코드 값에 의해서 정해집니다. 
(1) str1 < str2 인 경우에는 음수 반환
(2) str1 > str2 인 경우에는 양수 반환
(3) str1 == str2 인 경우에는 0을 반환 합니다.

출처: https://blockdmask.tistory.com/391 [개발자 지망생]

▶ 헤더파일
C언어 : <string.h>
C++ : <cstring>
▶ 정의
int strcmp(const char* str1, const char* str2)
int strncmp(const char* str1, const char* str2, size_t n);
출처: https://blockdmask.tistory.com/391 [개발자 지망생]

 

후위 표기법으로 변환 - 변환 함수 만들기

char* transition(Stack *stack, char **s, int size) {
    char res[1000] = ""; // 후위 표기법으로 바뀐 문자열이 res배열에 담길 것임
    for (int i= 0; i<size; i++){
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) { //s배열의 해당 원소가 연산자라면
            while(stack->top !=NULL && getpriority(getTop(stack)) >= getpriority(s[i])){ //stack의 top과 비교해서, top의 우선순위가 더 높거나 같다면(top값이 피연산자 or 더 우선 순위가 높은 연산자), 먼저 res배열에 top 값을 넣는다
                strcat(res,pop(stack)); strcat(res," "); //이때 각각의 항목이 띄어쓰기로 구분 된다
            }
            push(stack, s[i]); //스택에 s배열의 해당원소(i 인덱스를 가진)를 넣는다.
        }
        else if (!strcmp(s[i], "(")) push(stack,s[i]); //s[i]가 여는 괄호인 경우 바로 스택에 넣는다
        else if (!strcmp(s[i], ")")){
            while(strcmp(getTop(stack), "(")){
                strcat(res, pop(stack)); strcat(res," ");
            }
            pop(stack);
        }
        else { strcat(res, s[i]); strcat(res," "); } //일반숫자(피연산자)인 경우 바로 출력(s[i]를 " "로 구분해서 res배열에 넣는다
    }
    while (stack->top != NULL){
        strcat(res, pop(stack)); strcat(res," "); //stack에 남아있는 것 모두 res에 넣기(" ")로 구분
    }
    return res; //후위 표기법으로 변환된 res 배열을 반환
}

 

strcat 함수란?

함수 원형 : char* strcat(char* dest, const char* origin);

 

1) origin에 있는 문자열을 dest 뒤쪽에 이어 붙이는 함수 입니다.

2) dest 문자열 끝에 있는 '\0' 이것은 사라지고 그 위치에 origin이 바로 붙어버리는게 특징입니다.

3) strcat 간단한 사용법 

char origin[] = "BlockDMask";

char dest[20] = "aaabbb";

strcat(dest, origin);

 

결과 : "aaabbbBlockDMask"

출처: https://blockdmask.tistory.com/350 [개발자 지망생]

 

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

1. 피연산자가 들어오면 스택에 담는다.
2. 연산자를 만나면 스택에서 두개의 피연산자를 꺼내서 연산한 뒤, 그 결과를 스택에 담는다.
3. 연산을 마친 후 스택에 남아있는 하나의 피연산자가 연산 수행의 결과이다.

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],"/")){ //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/z; //꺼낸 피연산자를 계산. 스택의 구조상, y가 먼저 들어간 원소 이므로, 위와 같이 y를 앞에두어서 계산해야한다.
            char buffer[100]; //계산한 결과를 담을 버퍼
            sprintf(buffer, "%d", z); //계산 값(정수형)을 다시 문자열 형태로 바꾸어 버퍼에 담음
            push(stack, buffer); //계산 값을 스택에 다시 넣음
        }
        else{
            push(stack,s[i]); //s[i]가 숫자(피연산자)일 경우엔 바로 스택에 넣음 
        }
    }
    printf("%s\n",pop(stack)); //최종결과 출력(스택의 마지막 원소)
}

atoi = char to int = 문자열을 정수 타입으로
atof = char to double = 문자열을 실수 타입으로
atol = char to long int = 문자열을 long 정수 타입으로
중요한것은 여기서 char는 char[N], char* 로 표현이 되는 문자열을 말합니다.
개인적으로는 저는 char* to int 이 표현이 더 정확한 표현이라고 생각이 듭니다.

C++ 에서는 string 클래스에 의해서 문자열을 string으로 표현할 수 있는데, C언어에서는 string 클래스가 존재하지 않기 때문에 char 배열을 이용하여 문자열을 표현하기 때문입니다.

출처: https://blockdmask.tistory.com/331 [개발자 지망생]

 

만든 계산기 사용하기

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++; //공백을 만날때마다 문자열갯수 +1
    }
    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); // 각 문자열은 최대 100까지의 크기로 들어갈 수 있게 크기 할당
    }
    for(int i = 0; i <size; i++){
        strcpy(input[i],ptr); //토큰으로 분리된 각 문자열(ptr)을 계속 input 배열에 넣음
        ptr = strtok(NULL," "); // 계속해서 다음 토큰 불러옴
    }
    char b[1000] = "";
    strcpy(b, transition(&stack, input, size)); //input 문자열을 후위 표기법으로 바꾸어 b에 담기
    printf("후위 표기법 : %s\n", b);
    size = 1;
    for (int i = 0; i < strlen(b)-1; i++); { //마지막은 항상 공백이 들어가므로 1을 뺌
        if(b[1] ==' ') 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;
}