[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 41회차 미션

 

 

 

환급미션 41일째...

 

 

 

 

운영체제 - 자료구조와 알고리즘 - 스택을 활용한 계산기 만들기

운영체제 - 자료구조와 알고리즘 - 큐

 

 

목표 :

중위 표기법-> 후위 표기법으로 변환하는 방법

후위 표기법을 계산해 결과값 도출하는 방법

=> 스택 자료구조를 이용해 계산기 구현

 

 

 

 

- 중위 표기법

 

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

ex) 7 * 5 + 3  ===> 피연산자 사이에 연산자가 들어감

 

 

- 후위 표기법

 

컴퓨터가 계산하기 편한 표기방법

ex) 7 5 * 3 +  ===> 연산자가 뒤쪽에 위치

 

 

 

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

 

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

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

 

 

 

* 스택 구현하기 

 

 

------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

typedef struct Node

{

    char data[100]; //숫자는 길이가 길 수 있기 때문에 문자열로 처리

    struct Node *next; //다음노드로 연결될 수 있도록

} Node;

 

typedef struct Stack

{

    Node *top; //특정노드의 top 포인터를 정의

} Stack;

 

void push(Stack *stack, char *data) //입력된 데이터를 스택의 top에 넣어줌

{

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

}

--------------------

 

 

이제

실질적으로 후위 표기법으로 변환해주는 함수를 만들 것이다.

 

 

-------------------------------

char* transition(Stack *stack, char **s, int size) //s는 입력된 문자를 의미

//만약 37 + 5 라고 입력되었다면,

//"37","+","5" 총 3개의 문자열로 나누어서 들어오게 되는 문자열의 배열을 s가 됨

//size : 들어오는 문자열의 갯수

{

    char res[1000] = ""; //변환이 이루어진, 후위표기법으로 바뀐 결과가 담길 문자열

    for (int i=0; i<size; i++)

    {

        if (!strcmp(s[i], "+") || !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, " ");

            }

            //자신보다 우선순위가 높은 것들 먼저 스택에서 뽑은 뒤에

            //뽑은 데이터를 res에 넣고, 뒤에 한 칸 띄어쓰기 함.

            push(stack, s[i]);

            //자신을 스택에 넣음

        }

        // 만약 3 + 5를 이 함수에 넣게되면

        // 3 5 + 으로 출력될 수 있게 한다.

        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(stack);

        }

        else {strcat(res, s[i]); strcat(res, " ");} //일반 숫자인 경우, 바로 출력

    }

    while (stack->top != NULL) //스택에서 남은 원소가 있다면 모두 꺼내줌

    {

        strcat(res, pop(stack)); strcat(res, " ");

    }

    return res; //결과적으로 res를 반환해서 후위표기법으로 변환되는 것이다.

}

--------------------------

 

 

 

 

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

 

•피연산자가 들어오면 스택에 넣는다

•연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산, 결과를 스택에 담는다.

•연산이 끝나고 스택에 남아있는 하나의 피연산자가 연산 수행 결과이다.

 

 

 

--------------

void calculate(Stack *stack, char **s, int size)

// 만약 입력된 값이 3 5 + 였다면

// "3", "5", "+"가 문자열 원소로서 배열에 담겨서 s의 형태로 들어오게 된다.

{

    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)); //연산자를 만나면, 스택에서 2개를 뽑아서

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

    // size=1부터 출발해서 띄어쓰기가 나올 때마다 size++,

    // size == 각각의 문자열의 갯수

    char *ptr = strtok(a," ");

    //string.h에 있는 strtok 함수를 이용,

    //각각의 문자열을 띄어쓰기를 기준으로 token으로 분리를 한다.

    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 = strtok(NULL," ");

    }

    //token으로 분리된 각 문자열을 계속해서 input 배열에 넣는다.

    

    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[i]==' ') size++;

    char *ptr2 = strtok(b, " ");

    

    for (int i=0; i<size; i++)

    {

        strcpy(input[i], ptr2);

        ptr2 = strtok(NULL, " ");

    }

    //해당 후위 표기식에 포함되어있는 문자열도 띄어쓰기를 기준으로 token으로 분리

    //다시 input으로 넣어준다.

    

    calculate(&stack, input, size);

    //계산&결과출력

    

    return 0;

}

---------------------------------------

 

 

여기까지 

스택을 활용해서 계산기를 만들어보았고

출력값은 아래와 같다.

 

 

 

 

 

 

 

운영체제 - 자료구조와 알고리즘 - 큐

 

큐 자료구조의 개념&활용방법 이해

c언어로 큐 자료구조 구현

 

 

 

- 큐 (Queue)

 

•뒤쪽으로 들어가서 앞쪽으로 나오는 자료구조 (FIFO를 생각하면 될듯)

•스케쥴링, 알고리즘 등에서 다방면으로 활용됨

•배열을 이용한 구현

•연결리스트를 이용한 구현

•기본적인 형태의 자료구조, 구현 난이도 낮은 편

 

push : 큐에 데이터를 넣음

pop : 큐에서 데이터를 빼냄

 

 

큐에서 연산결과는 위의 그림과 같다.

( 스택에서는 결과가 7 5 가 된다. )

 

 

 

 

- 배열을 이용한 큐 구현

 

 

* 큐의 선언

 

------------

#include <stdio.h>

#define SIZE 10000

#define INF 99999999

 

int queue[SIZE];

int front = 0;

int rear = 0;

//앞,뒤는 0인덱스를 가리킬 수 있도록 선언

-----------------

 

 

* 큐 삽입함수

 

 ---------------

void push(int data)

{

    if (rear>=SIZE)//SIZE보다 크다면 더이상 들어갈 공간이 없으므로 오버플로우 출력

    {

        printf("queue overflow\n");

        return;

    }

    queue[rear++] = data;

    //큐는 뒤에서부터 들어오기 때문에

}

-------------------

 

 

* 큐 추출함수

 

----------------------

int pop()

{

    if (front==rear)//front==rear라면 더이상 추출할 수 없으므로 언더플로우 출력

    {

        printf("queue underflow\n");

        return -INF;

    }

    return queue[front++];//큐에서 프론트에 해당하는 값을 꺼낸 뒤에 1을 더해서 하나의 값이 꺼내졌다는 것을 확인

}

--------------------------

 

 

 

* 큐 전체 출력 함수

 

 

-----------------------

void show()

{

    printf("--- 큐의 앞 ---\n");

    for (int i=front; i<rear; i++)

        printf("%d\n", queue[i]);

    printf("--- 큐의 뒤 ---\n");

}

---------------------------

 

 

 

* 완성된 큐 사용해보기

 

 

------------------------

int main(void)

{

    push(7);

    push(5);

    push(4);

    pop();

    push(6);

    pop();

    show();

    

    return 0;

}

----------------------------

 

 

 

 

출력값은 아래와 같다.

 

 

 

 

 

 

- 연결리스트 이용한 큐 구현

 

 

* 큐의 선언

 

 

--------------

#include <stdio.h>

#include <stdlib.h>

#define INF 99999999

 

typedef struct Node

{

    int data;

    struct Node *next;

} Node;

 

typedef struct Queue //큐 구조체

{

    Node *front;

    Node *rear;

    int count; //큐에 포함된 원소들의 갯수 카운트

} Queue;

-----------------

 

 

 

* 큐의 삽입과정

 

 

 

 

삽입할 노드 마련 후,

기존에 Rear를 가리키고 있는 노드가 가리키도록 만들고,

Rear의 위치를 변경한다.

 

 

 --------------------

 void push(Queue *queue, int data)

{

    Node *node = (Node*)malloc(sizeof(Node));

    node->data = data;

    node->next = NULL;

    if (queue->count==0)

        queue->front = node;

    else

        queue->rear->next=node;

    queue->rear=node;

    queue->count++;

}

----------------------

 

 

 

 

* 큐의 추출 과정

 

 

 

( 큐에서는 앞에서부터 꺼낸다. )

이전 Front가 가리키던 다음 노드가 Front가 되도록 하고,

삭제할 노드를 메모리 해제

 

 

-------------------------

int pop(Queue *queue)

{

    if (queue->count ==0) //큐가 비어있을 때 언더플로우 발생

    {

        printf("queue underflow\n");

        return -INF;

    }

    Node *node = queue->front;

    int data = node->data; //데이터를 추출

    queue->front = node->next; //큐의 프론트가 다음 노드를 가리킬 수 있도록

    free(node);

    queue->count--;

    return data; //데이터를 반환

}

----------------------------

 

 

 

 

* 큐 전체 출력 함수

 

 

-------------------

void show(Queue *queue)

{

    Node *cur = queue->front;

    //큐의 프론트에서부터 데이터를 한 개씩 확인해가면서 출력할 것임

    printf("--- 큐의 앞 ---\n");

    while (cur != NULL)

    {

        printf("%d\n", cur->data);

        cur = cur->next;

    }

    printf("--- 큐의 뒤 ---\n");

}

 

-------------------

 

 

 

* 완성된 큐를 사용하기

 

 

-------------------

int main(void)

{

    Queue queue;

    queue.front = queue.rear = NULL;

    //큐를 초기화

    queue.count = 0;

    

    push(&queue, 7);

    push(&queue, 5);

    push(&queue, 4);

    pop(&queue);

    push(&queue, 6);

    pop(&queue);

    show(&queue);

    

    return 0;

}

-------------------

 

 

 

 

출력결과는 아래와 같다.

배열을 이용하여 큐를 구현했을 때와 동일한 결과가 출력된다.

 

 

 

 

 

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE