4장 연습문제 #10, #11, #12

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

//스택코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

//스택초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

//공백상태 검출함수
int is_empty(StackType* s)
{
	return (s->top == -1);
}

//포화상태 검출함수
int is_full(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}

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

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

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

int main(void)
{
	StackType s;
	int size;
	int array[MAX_STACK_SIZE];
	init_stack(&s);

	printf("정수 배열의 크기: ");
	scanf("%d", &size);

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

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

 

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

//스택코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef struct {
	char c;
	int n;
}element;

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

//스택초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

//공백상태 검출함수
int is_empty(StackType* s)
{
	return (s->top == -1);
}

//포화상태 검출함수
int is_full(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}

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

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

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

int check_matching(const char* in) {
	StackType s;
	char ch, open_ch;
	int pnumber = 0;
	int i, n = strlen(in);
	element data;
	init_stack(&s);

	for (int i = 0; i < n; i++) {
		ch = in[i];//ch=다음문자
		switch (ch) {
		case '(': case'[': case'{':
			printf("%d ", ++pnumber);
			data.c = ch;
			data.n = pnumber;
			push(&s, data);
			break;
		case')': case']': case'}':
			if (is_empty(&s)) return 0;
			else {
				data = pop(&s);
				open_ch = data.c;
				if ((open_ch == '(' && ch != ')') ||
					(open_ch == '{' && ch != '}') ||
					(open_ch == '[' && ch != ']')) {
					return 0;
				}
				printf("%d ", data.n);
				break;
			}
		}
	}
	if (!is_empty(&s))return 0;
	return 1;
}

int main(void)
{
	char line[100];
	printf("수식: ");
	gets_s(line, 100);
	printf("괄호수: ");
	check_matching(line);
	return 0;
}

 

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

[알고리즘]

1) 초기 상태에서 스택은 비어있으며 아무 문자도 비교할 수 없습니다. 이때 letter_count 변수를 1로 초기화하여 현재 문자열의 길이를 1로 설정합니다.
2)현재 문자 line[i]와 스택의 최상위 문자를 비교하여 같으면 letter_count를 증가시킵니다. 이렇게 하면 연속된 문자열의 길이를 계속 늘려가게 됩니다.
3)만약 현재 문자와 스택의 최상위 문자가 다르다면, 이전에 연속된 문자열이 끝났음을 의미하고, 그 이전 문자열의 길이와 문자를 출력한 후, letter_count를 1로 초기화하여 현재 문자열의 길이를 다시 시작합니다.

//스택코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

//스택초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

//공백상태 검출함수
int is_empty(StackType* s)
{
	return (s->top == -1);
}

//포화상태 검출함수
int is_full(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}

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

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

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


void main()
{
	int letter_count;
	char top;
	char line[100];
	StackType s;

	init_stack(&s);

	printf("문자열: "); //사용잘부터 문자열 입력받기
	gets_s(line, 100);

	for (int i = 0; line[i]; i++) { //소문자로 변환저장
		line[i] = tolower(line[i]);
	}

	for (int i = 0; i < strlen(line); i++) {
		if (is_empty(&s))
			letter_count = 1;
		if ((s.top + 1) > 0) {
			top = peek(&s);

			if (top == line[i]) {
				letter_count++;
			}
			if (top != line[i] || i == strlen(line) - 1) {
				printf("%d", letter_count);
				printf("%c", top);
				letter_count = 1;
			}
		}
		push(&s, line[i]);
	}
}