10개의 임의의 정수를 단순 연결리스트의 리스트에 담고 최솟값과 최댓값을 찾는 간단한 문제입니다.

최솟값과 최댓값을 찾는 pivot(시작 비교 할 값)을 리스트의 첫번째 원소로 지정하여 리스트를 탐색하여 값을 반환합니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct ListNode {     // 노드 타입
    int data;
    struct ListNode* link;
} ListNode;
 
// 오류 처리 함수
void error(char* message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
void insert_last(ListNode** head, int value)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    if (p == NULL)return;
    p->data = value; p->link = NULL;
    if (*head == NULL)
        *head = p;
    else
    {
        ListNode* temp = *head;
        while (temp->link != NULL)
            temp = temp->link;
 
        temp->link = p;
    }
}
int check_minval(ListNode*head)
{
    ListNode* temp = head;
    int min_val = temp->data;
    for (temp; temp != NULL; temp = temp->link)
        if (min_val > temp->data)
            min_val = temp->data;
    return min_val;
}
int check_maxval(ListNode*head)
{
    ListNode* temp = head;
    int max_val = temp->data;
    for (temp; temp != NULL; temp = temp->link)
        if (max_val < temp->data)
            max_val = temp->data;
    return max_val;
}
 
// 테스트 프로그램
int main(void)
{
    ListNode* head = NULL;
    int data;
    int max_val, min_val;
    //10개의 숫자를 넣기
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &data);
        insert_last(&head, data);
    }
    min_val = check_minval(head);
    max_val = check_maxval(head);
    printf("최솟값은 %d, 최댓값은 %d입니다.\n", min_val, max_val);
    return 0;
}
 
cs


결과


저작자표시

'자료구조 > 리스트' 카테고리의 다른 글

헤드노드를 이용하지않는 이중연결리스트의 구현  (0) 2020.05.16
헤드노드를 이용한 이중연결리스트의 구현  (0) 2020.05.16
원형연결리스트 삽입 구현하기(맨앞,중간,맨뒤)  (0) 2020.04.29
학생정보를 담은 단순연결리스트 구현하기  (0) 2020.04.22


5명의 학생 정보를 저장하는 단순연결리스트를 구현해봤습니다.

첫노드, 특정 노드의 앞,뒤, 맨 끝 노드 삽입 등의 경우를 고려하지않고 단순히 입력데이터를 맨 끝에 추가하였습니다.


주의

아래 코드와 같은 구현의 insert함수에서 이중 포인터가 아닌 단순1차원 포인터를 사용하면 정답이 출력되지않습니다.

이유는 1차원 포인터 사용 시 insert함수 내부에서 main문의 head가 아닌 새로운 head변수를 이용하므로

즉, 주소값이 아닌 값을 이용한 call by value 형식이므로 함수내부에서 함수내부의 새로운 head로 연산이 진행될 뿐

main문의 head에는 영향이 없습니다.

즉, 최초에 비어있는 리스트에 1차원포인터로 insert함수에 인자를 넘겨주면 연산 후 main문의 head는 여전히 NULL상태가 됩니다. 

따라서 2차원 포인터로 주소값을 받아 함수 내부에서 head를 변경 시킬 수 있도록 해야합니다.

1차원 포인터를 쓰고싶다면 insert 함수에서 사용한 head를 ListNode*형으로 반환하여 main문에서 사용하면됩니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char name[10];
    int age;
    int height;
} element;
 
typedef struct ListNode {     // 노드 타입
    element data;
    struct ListNode* link;
} ListNode;
 
// 오류 처리 함수
void error(char* message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
void insert_last(ListNode** head, element value)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    if (p == NULL)return;
    p->data = value; p->link = NULL;
    if (*head == NULL)
        *head = p;
    else
    {
        ListNode* temp = *head;
        while (temp->link != NULL)
            temp = temp->link;
 
        temp->link = p;
    }
}
 
void print_list(ListNode* head)
{
    for (ListNode* p = head; p != NULL; p = p->link)
        printf("이름:%s 나이:%d 키%d \n", p->data.name, p->data.age, p->data.height);
}
 
// 테스트 프로그램
int main(void)
{
    ListNode* head = NULL;
    element data;
    //5명의 학생 정보 입력받기
    for (int i = 0; i < 5; i++)
    {
        scanf("%s %d %d", data.name, &(data.age), &(data.height));
        insert_last(&head, data);
    }
    print_list(head);
    return 0;
}
 
cs


결과





저작자표시

'자료구조 > 리스트' 카테고리의 다른 글

헤드노드를 이용하지않는 이중연결리스트의 구현  (0) 2020.05.16
헤드노드를 이용한 이중연결리스트의 구현  (0) 2020.05.16
원형연결리스트 삽입 구현하기(맨앞,중간,맨뒤)  (0) 2020.04.29
단순 연결리스트에서 정렬된 값 찾기  (0) 2020.04.22


제가갖고있는 2권의 자료구조책에서는 오로지 리스트로만 구현한 덱 밖에없었습니다.

현재 수강중인 자료구조에서는 교수님께서 원형큐를 응용한 덱구현 프로그램을 올려주셨는데 

확실히 리스트로 구현한 것보다 연산이 헷갈리고 어려운 것 같습니다.(이 이유때문에 책에 내용이없는것 아닐까 싶습니다.)


원형큐를 이용한 덱은 기존의  큐에서 아주 살짝만 응용하면 됩니다.

front 와 rear는 똑같이 0부터 시작하고 연산은 다음과 같습니다.

add_front: 꽉찼는지 확인 후 front 자리에 삽입 후 front=(front-1+MAX_SIZE)%MAX_SIZE;

add_rear:  꽉찼는지 확인 후 원형 큐의 enqueue와 동일

delete_front: 원형큐의 dequeue와 동일

delelte_rear: 현재 rear자리의 값 임시 저장 후 rear=(rear-1+MAX_SIZE)%MAX_SIZE 연산 후 임시 저장했던 rear자리 값 반환



즉, 한칸을 비워놓는것은 똑같고 add_front연산 후 front의 위치는 삽입한 자리 한칸 앞을 가리킵니다.



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
/*
add_front로 1~3까지 삽입 후 각각 출력하고 
delete_rear로 모두 삭제하고 출력하기
//front 와 rear 위치 잘 보기
rear 1삽입
*/
#define MAX_SIZE 5
typedef struct
{
    int Dqueue[MAX_SIZE];
    int front, rear;
}DQType;
void init(DQType* q)
{
    q->front = q->rear = 0;
}
int is_full(DQType* q)
{
    return ((q->rear + 1) % MAX_SIZE == q->front);
}
 
int is_empty(DQType* q)
{
    return q->front == q->rear;
}
void add_front(DQType* q, int data)
{
    if (is_full(q))
    {
        fprintf(stderr, "요소가 꽉 찼습니다.\n");
        return;
    }
    q->Dqueue[q->front] = data;
    q->front = (q->front - 1+MAX_SIZE) % MAX_SIZE;
}
void delete_rear(DQType* q)
{
    if (is_empty(q))
    {
        fprintf(stderr, "요소가 없습니다.\n");
        return;
    }
    int now = q->rear;
    q->rear = (q->rear - 1+MAX_SIZE) % MAX_SIZE;
    //반환형 사용시 q->DQeue[now] 반환
}
void deque_print(DQType* q)
{
    if (!is_empty(q))
    {
        printf("DEQUE연산: (front=%d rear=%d)= ", q->front, q->rear);
        int i = q->front;
        do {
            i = (i + 1) % MAX_SIZE;
            //한번은 출력 하고 empty여부판단해야됨
            printf("%d |  ", q->Dqueue[i]);
            //비어있으면 탈출해야됨
            if (i == q->rear)break;
            //모든원소를 출력할 때 까지
        } while (i != q->front);
    }
    printf("\n");
}
int main(void) {
    DQType q;
    init(&q);
    for (int i = 0; i < 3; i++) {
        add_front(&q, i+1);
        deque_print(&q);
    }
    for (int i = 0; i < 3; i++) {
        delete_rear(&q);
        deque_print(&q);
    }
    return 0;
}
cs



결과





저작자표시


사이즈5인 큐에 1->2->3->4순으로 삽입후 

5번째 요소를 넣을 때 정상적으로 삽입됨을 확인하고 모든 원소 삭제를 삭제 후 현재 front와 rear변수 위치 확인하기 


핵심

1.원형큐는 최초의 한칸 (0번째 배열인덱스자리)을 비워둔다.

최초의 front ,rear 위치

선형큐: front==rear==-1

배열큐: front==rear==0


3. 사소한 실수 조심하기

선형큐 때는 연산 시 return 문을 한줄로 표현할 수 있었는데 

원형큐에서 삽입/삭제 연산 시 아래와 같이 작성하면 어떻게될까요?

q->Queue[(q->rear + 1) % MAX_SIZE]=data;

=> rear는 증가하지않고 1번 째 자리에 원소를 대입합니다.

결국에는 이러한 연산을 100번해도 1번째 자리에 원소를 100번 연산하는 꼴이됩니다.

그렇기 때문에  2줄로 나눠서 코드를 작성해야합니다.


q->rear=q->(rear+1)%MAX_SIZE;

q->Queue[q->rear]=data;



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
/*사이즈5인 큐에 1->2->3->4순으로 삽입후
5번째 요소를 넣을 때 정상적으로 삽입됨을 확인하고 모든 원소 삭제를 삭제 후 현재 front와 rear변수 위치 확인하기*/
#define MAX_SIZE 5
typedef struct
{
    int Queue[MAX_SIZE];
    int front, rear;
}QType;
void init(QType* q)
{
    q->front = q->rear = 0;
}
int is_full(QType* q)
{
    return ((q->rear + 1) % MAX_SIZE == q->front);
}
void enQueue(QType* q, int data)
{
    if (is_full(q))
    {
        fprintf(stderr, "꽉 차서 원소를 삽입할 수 없어요..\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->Queue[q->rear]=data;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int deQueue(QType* q)
{
    if (is_empty(q))
    {
        fprintf(stderr, "큐가 비어서 삭제할 수 없습니다..\n");
        exit(1);
    }
    q->front = (q->front + 1) % MAX_SIZE;
    return q->Queue[q->front];
}
int main()
{
    QType q;
    int data;
    init(&q);
    //5개 요소를 꽉차지않을 때 까지(5개)삽입하기
    int i = 1;
    while (!is_full(&q))
    {
        printf("%d번째 원소를 삽입합니다.\n", i++);
        scanf("%d", &data);
        enQueue(&q, data);
    }
    //5번째 원소삽입-> 오류
    enQueue(&q, data);//-> 오류메시지출력
    while (!is_empty(&q))
        printf("%d을 삭제합니다.\n", deQueue(&q));
    
    printf("현재 front와 rear의 위치는(인덱스 자리는) 각각 %d %d입니다.\n", q.front, q.rear);
    return 0;
}
cs



결과


저작자표시

'자료구조 > 큐' 카테고리의 다른 글

선형 큐(배열 큐) 구현하기  (0) 2020.04.16


사이즈5인 큐에 1->2->3->4->5순으로 삽입후  6번째 요소를 넣을 때 오류메시지를 출력하고

1,2 원소 삭제 후 남아있는 모든원소를 출력하기



핵심

1. 큐 사이즈 만큼 입력받을 때 

큐사이즈만큼 데이터를 입력받을 때 아래 코드에 나와있는 반복문처럼 원소를 삽입하면 됩니다.


2. 불필요한 코드 줄이기

모든 연산 함수의 return문을 보면 두번, 세번 쓸 코드를 한 코드로 표현할 수 있음을 알 수 있습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
 
//    사이즈5인 큐에 1->2->3->4->5순으로 삽입후 
//  6번째 요소를 넣을 때 오류메시지 출력하고 1,2 원소 삭제 후 남아있는 원소 출력
#define MAX_SIZE 5
typedef struct
{
    int Queue[MAX_SIZE];
    int front, rear;
}QType;
void init(QType* q)
{
    q->front = q->rear = -1;
}
int is_full(QType* q)
{
    return q->rear == MAX_SIZE - 1;
}
void enQueue(QType* q, int data)
{
    if (is_full(q))
    {
        fprintf(stderr, "꽉 차서 원소를 삽입할 수 없어요..\n");
        return;
    }
    q->Queue[++(q->rear)] = data;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int deQueue(QType* q)
{
    if (is_empty(q))
    {
        fprintf(stderr, "큐가 비어서 삭제할 수 없습니다..\n");
        exit(1);
    }
    return q->Queue[++(q->front)];
}
int main()
{
    QType q;
    int data;
    init(&q);
    //5개 요소를 꽉차지않을 때 까지(5개)삽입하기
    int i = 1;
    while (!is_full(&q))
    {
        printf("%d번째 원소를 삽입합니다.\n", i++);
        scanf("%d", &data);
        enQueue(&q, data);
    }
    //6번째 원소삽입-> 오류
    enQueue(&q, data);//-> 오류메시지출력
    printf("삭제한 원소는 %d입니다.\n", deQueue(&q));
    printf("삭제한 원소는 %d입니다.\n", deQueue(&q));
    for (int i = q.front+1; i <= q.rear; i++)
    {
        printf("큐에 남아있는 원소는%d\n",q.Queue[i]);
    }
    return 0;
}
cs



결과




저작자표시

'자료구조 > 큐' 카테고리의 다른 글

원형 큐 구현하기  (0) 2020.04.17


후위식 계산프로그램은 피연산자를 스택에 push하고 연산자를 만났을 때 pop하여 연산 후 다시 push하는 과정이었지만

중위수식을 후위식으로 변환하는 프로그램은 반대로 연산자를 push하고 피연산자는 그대로 출력합니다.


중위 수식을 후위 수식으로 변환할 떄 중요한 것은 연산자의 우선순위입니다.

괄호와 숫자로 구성된 중위 수식을 후위 수식으로 변환 할 때 연산자의 순위는 다음과 같습니다.


괄호 < +, - 연산자 < *, / 연산자


가장 중요한 것은 현재 처리중인 연산자와 스택에 있는 연산자의 우선순위를 이용한 처리 입니다.


1. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 낮을 때 

예를들어) 처리중인 연산자: + or - ,  스택에있는 연산자: * or / 일 때

=> 스택에 있는 연산자를 pop 해서 출력 후 처리 중인 연산자를 push 합니다.


2. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 클 때

예를들어) 처리중인 연산자: * or / , 스택에 있는 연산자: +, - 일 때

=> 현재 처리 중인 연산자를 그냥 push합니다.


3. 현재 처리중인 연산자의 우선순위와 스택에 있는 연산자의 우선순위가 같을 때

예를들어) 처리중인 연산자: +, 스택에 있는 연산자: - 일 때

=> 1번 경우와 똑같이 처리한다.

이유는 간단한 예시를 들면 쉽게 알 수 있습니다.

ex) 5-4+3일 때, 5/4*3 일 때 

=> 우선순위를 어떻게 하느냐에 따라 답이 달라집니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, char x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
char peek(stackType* s);
void infix_to_postfix(const char* s);
int prec(char op);
int main()
{
    
    infix_to_postfix("(2+3)*4+9");
    return 0;
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, char x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
char peek(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다.\n");
        exit(1);
    }
    return s->data[(s->top)];
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
void infix_to_postfix(const char* s)
{
    char ch,top_op;
    int n = strlen(s);
    stackType st;
    init(&st);
    for (int i = 0; i < n; i++)
    {
        ch = s[i];
        switch (ch)
        {
        case '+': case '-':case '*':case '/':
            while (!is_empty(&st) && (prec(ch) <= prec(peek(&st))))
            {
                printf("%c", pop(&st));
            }
            push(&st, ch);
            break;
        case '(':
            push(&st, ch);
            break;
        case ')':
            top_op = pop(&st);
            while (top_op != '(')
            {
                printf("%c", top_op);
                top_op = pop(&st);
            }
            break;
            //숫자일 떈 그대로 출력
        default:
            printf("%c", ch);
            break;
        }
    }
        //아직 스택에 남아있다면 다 뽑아냄
        while (!is_empty(&st))
            printf("%c", pop(&st));
    
}
int prec(char op)
{
    switch (op)
    {
    case '(':case ')': return 0;
    case '+':case '-': return 1;
    case '*':case '/':return 2;
    }
    return -1;
}
 
cs


결과





저작자표시

'자료구조 > 스택' 카테고리의 다른 글

스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


주의할 것은 스택에 있는 피연산자를 뽑아낼 때 op1, op2의 순서입니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, int x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
int eval(const char* s);
int main()
{
    int result;
    puts("82/3-32*+ 계산하기\n");
    result = eval("82/3-32*+");
    printf("결과값은%d\n", result);
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, int x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
int eval(const char* s)
{
    int op1, op2, value;
    int len = strlen(s);
    char ch;
    stackType st;
    init(&st);
    for (int i = 0; i < len; i++)
    {
        ch = s[i];
        if (ch != '+' && ch != '*' && ch != '/' && ch != '-')
        {
            value = ch - '0';
            push(&st, value);
        }
        else
        {
            //op1, op2 순서 조심, op2가 최근에 넣은 피연산자임
            op2 = pop(&st);
            op1 = pop(&st);
            switch (ch)
            {
            case '+': push(&st,op1 + op2); break;
            case '-':push(&st,op1 - op2); break;
            case '*': push(&st,op1 * op2); break;
            case '/': push(&st,op1 / op2); break;
            }
        }
    }
    return pop(&st);
 
}
cs


결과




저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


괄호가 들어간 문장을 입력하고 괄호가 올바르게 표현되었을 때와 틀렸을 때를 표현하는 프로그램 만들기

주의: 띄어쓰기 들어간 문자열의 입력? fgets함수사용하기 (gets함수는 비표준함수라 사용X)



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, int x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
int main()
{
    stackType s;
    char exp[20];
    fgets(exp, sizeof(exp), stdin);
    if (check(exp) == 1)
        puts("성공!");
    else
        puts("실패!");
    return 0;
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, int x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
int check(char* exp)
{
    stackType s;
    char ch, open_ch;
    int n = strlen(exp);
    init(&s);
    for (int i = 0; i < n; i++)
    {
        ch = exp[i];
        switch (ch)
        {
        case '(':case '[':case'{':
            push(&s, ch);
            break;
        case ')':case']':case'}':
            if (is_empty(&s))return 0;
            else
            {
                open_ch = pop(&s);
                if ((open_ch == '(' && ch != ')') || (open_ch == '{' && ch != '}') ||
                    (open_ch == '[' && ch != ']'))
                    return 0;
                
            }
            break;
        }
    }
    //괄호검사 다했는데 스택에 원소가 남아있다면? => 잘못된 수식
    if (!is_empty(&s))return 0;
    return 1;
}
cs


결과





저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09

+ Recent posts

티스토리툴바