[쉽게 풀어 쓴 자료구조] 4장 연습문제 EXERCISE (programming)

10. 배열에 들어 있는 정수이 순서를 거꾸로 한느 프로그램을 작성해보자. 스택을 사용한다.

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

typedef int element;

typedef struct {
	element* data;
	int top;
	int size;
}StackType;

void init_stack(StackType* s, int size) {
	s->top = -1;
	s->size = size;
	s->data = (element*)malloc(sizeof(element) * size);
}

int is_empty(StackType* s) {
	return s->top == -1;
}
int is_full(StackType* s) {
	return s->top == (s->size - 1);
}

void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return 0;
	}
	else s->data[++(s->top)] = item;
}

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

int main() {
	StackType s;
	int size, n;
	
	printf("정수 배열의 크기: ");
	scanf("%d", &size);
	init_stack(&s, size);

	printf("정수를 입력하시오: ");
	for (int i = 0; i < size; i++) {
		scanf("%d", &n);
		push(&s, n);
	}

	printf("반전된 정수 배열: ");
	for (int i = 0; i < size; i++) {
		printf("%d ", pop(&s));
	}

}

---

11. 수식에 있는 괄호의 번호를 출력하는 프로그램을 작성하라. 왼쪽 괄호가 나올 때마다 괄호 번호는 하나씩 증가한다. 오른쪽 괄호가 나오면 매칭되는 왼쪽 괄호 번호를출력한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

void count(const char* exp) {
	StackType s;
	int c = 0;
	char ch;

	init_stack(&s);

	for (int i = 0; exp[i] != '\0'; i++) {
		ch = exp[i];
		switch (ch) {
		case '(': 
			printf("%d ",++c);
			push(&s, c);
			break;

		case ')':
			printf("%d ", pop(&s));
		}
	}
}

int main() {
	char exp[100];
	printf("수식: ");
	scanf("%s", exp);
	printf("괄호 수: ");
	count(exp);

}

 

---

12. 다음과 같이 문자열을 압축하는 프로그램을 작성하라. "4a3b"는 'a'가 4개, 'b'가 3개 있다는의미이다. 이러한 압축 방법을 런길이(run length) 압축이라고 한다. 솜누자와 대문자는 구별하지 않는다. 압축된 문자열에서는 소문자로 출력한다. 스택의 peek() 연산을고려보자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "stack.h"

void run_length(char* str) {
	StackType s;
	char ch, op_ch;
	int count = 0;
	init_stack(&s);

	for (int i = 0; str[i] != '\0'; i++) {
		ch = tolower(str[i]);
		if (is_empty(&s) || ch == peek(&s)) {
			push(&s, ch);
			count++;
		}
		else {
			while (!is_empty(&s)) {
				op_ch = pop(&s);
			}
			printf("%d%c", count, op_ch);
			push(&s, ch);
			count = 1;
		}
	}
	printf("%d%c", count, pop(&s));
}


int main() {
	char str[100];
	printf("문자열을 입력하시오: ");
	scanf("%s", str);
	printf("압축된 문자열: ");
	run_length(str);
}

---

13. 주어진 정수에서 반복되는숫자를 제거하는 프로그램을 작성해보자. 스택 사용을 고려해보자.

 

(1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "stack.h"

void except(char* str) {
	StackType s;
	char ch, op_ch;

	init_stack(&s);

	while (*str != '\0') { // *str 도 가능
		ch = *str++;
		if (is_empty(&s) || ch != peek(&s)) {
			push(&s, ch);
			printf("%c", ch);
		}
	}
}

int main() {
	char str[100];
	printf("정수를 입력하시오: ");
	scanf("%s", str);
	printf("출력: ");
	except(str);
}

 

(2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "stack.h"

void except(char* str) {
	StackType s;
	char ch, op_ch;

	init_stack(&s);

	while (*str != '\0') { // *str 도 가능
		ch = *str++;
		if (is_empty(&s) || ch == peek(&s)) {
			push(&s, ch);
		}
		else {
			while (!is_empty(&s))
				op_ch = pop(&s);
			printf("%c", op_ch);
			push(&s, ch);
		}
	}
	printf("%c", pop(&s));
}

int main() {
	char str[100];
	printf("정수를 입력하시오: ");
	scanf("%s", str);
	printf("출력: ");
	except(str);
}

---

14. 배열로 구현된 수택에 저장된요소의 수를반환하는 size연산을 구현하여 보라.

(1)

int size(StackType* s) {
	return s->top + 1; 
}

 

(2) 근데 이러면 스택 요소 다 사라지는데? -> 1번이 옳은 방법

int size(StackType* s) {
	int count = 0;
	while (!is_empty(s)) {
		pop(&s);
		count++;
	}
	return count;
}

---

15. 미로 탐색 프로그램에서 탐색 성공 시에 입구부터 출구까지의 경로를 출력하도록 수정하라.

(스택을 하나더 사용해서 here의 위치를 저장한 후 빼내면 된다.) ???

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <windows.h>
#include "stack.h"
#define MAX_SIZE 6

//typedef struct {
//	short r;
//	short c;
//}element;

element here, entry = { 1, 0 };


char maze[MAX_SIZE][MAX_SIZE] = {
	{'1','1','1','1','1','1'},
	{'e', '0','1','0','0','1'},
	{'1','0','0','0','1','1'},
	{'1','0','1','0','1','1'},
	{'1','0','1','0','0','x'},
	{'1','1','1','1','1','1'},
};

void print_maze() {
	printf("\n");
	for (int i = 0; i < MAX_SIZE; i++) {
		for (int j = 0; j < MAX_SIZE; j++) {
			printf("%c", maze[i][j]);
		}
		printf("\n");
	}
}

void push_loc(StackType* s, int r, int c) {
	if (r < 0 || c < 0 || r > MAX_SIZE -1 || c > MAX_SIZE -1) return 0;
	if (maze[r][c] != '1' && maze[r][c] != '.') {
		element temp = { r,c };
		push(s, temp);
	}
}

int main() {
	StackType s;
	StackType root;
	element r1;
	int r, c;
	init_stack(&s);
	init_stack(&root);

	print_maze();

	here = entry;
	while (maze[here.r][here.c] != 'x') {
		Sleep(1000);
		push(&root, here);
		r = here.r;
		c = here.c;
		maze[r][c] = '.';
		system("cls");
		print_maze();
		push_loc(&s, r+1,c);
		push_loc(&s, r-1, c);
		push_loc(&s, r, c+1);
		push_loc(&s, r, c-1);

		if (is_empty(&s)) {
			printf("실패\n");
			return 0;
		}
		else {
			here = pop(&s);
		}
	}
	printf("성공\n");
	while (!is_empty(&root)) {
		r1 = pop(&root);
		printf("(%d %d) ", r1.r, r1.c);
	}
}