Stack, Queue 응용

Problem 3: 주어진 희소행열을 표현하기 위한 적합한 자료구조를 기술하고 행열 내 모든 값의 합을 구하는 독립된 함수를 작성하시오.

1. 정수값을 입력 받아 희소행렬의 크기를 결정

2. 주어진 행렬내 원소의 약 10% 이하가 0이 아닌 값으로 임의 수를 생성 하여 대입

//h.h




int** insertRand(int** Matrix, int m);
int* NoDupRand(int* rand_num, int n);
int** createMatrix(int m, int n);
void printMatrix(int** Matrix, int m);
void showPercent(int** matrix, int m1);
void SumMatrix(int** matrix, int SparesMatrix_row);

//f.c


#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
#include"h.h"

void SumMatrix(int** matrix, int SparesMatrix_row) {

	int m1, sum, size;
	sum = 0;
	size = SparesMatrix_row;
	//matrix[] 갯수
	for (m1 = 0; m1 < size; m1++) {
		sum += matrix[m1][2];
	}
	printf("==================\n");
	printf("sum is %d\n", sum);
	printf("==================\n");
}

void showPercent(int** matrix, int matrix_size) {
	int spares_size = matrix_size;
	spares_size -= matrix[matrix_size - 1][3];
	matrix_size /= 10;
	float percent;

	percent =((float)spares_size / (float)matrix_size);
	//행렬안에 값이 0인 경우를 빼줌
	printf("Percent : %0.3f%%\n", percent);
	printf("==================\n");

}

void printMatrix(int** Matrix, int m) {
	int m1, n1;
	for (m1 = 0; m1 < m; m1++) {
		for (n1 = 0; n1 < 3; n1++) {
			if (n1 == 2) {
				printf("|%4d|\n", Matrix[m1][n1]);
			}
			else
				printf("|%4d ", Matrix[m1][n1]);
		}
	}
}
//중복되지 않는 랜덤값을 가져오기위해
int* NoDupRand(int* rand_num, int n) {
	int index1, index2, i, temp;
	srand(time(NULL));

	//n번
	for (i = 0; i < n; i++) {
		rand_num[i] = i;
	}
	//섞기 n/2번
	for (i = 0; i < (n / 2); i++) {
		index1 = rand() % n;
		index2 = i;
		temp = rand_num[index1];
		rand_num[index1] = rand_num[index2];
		rand_num[index2] = temp;
	}
	return rand_num;
}
//(m x n) matrix
int** insertRand(int** Matrix, int m) {
	int m1, n1;
	int count;
	int* NoDupRand_m;
	int* NoDupRand_n;

	NoDupRand_m = (int*)malloc(sizeof(int) * m);
	NoDupRand_n = (int*)malloc(sizeof(int) * m);

	NoDupRand_m = NoDupRand(NoDupRand_m, m);
	sleep(1);
	NoDupRand_n = NoDupRand(NoDupRand_n, m);
	//원소를 넣을 (행,열)위치 생성
	for (m1 = 0; m1 < m; m1++) {
		//행(0~m-1) 열(0~n-1) 위치 저장
		//랜덤값 중복체크를 하면 시간, 공간복잡도가 늘어남으로
		//행과 열이 겹치는 경우
		//    행 열 값  행 열값
		//ex) [1][1][] [1][1][]
		Matrix[m1][0] = NoDupRand_m[m1];
		Matrix[m1][1] = NoDupRand_n[m1];
	}
	/*   0  1   3
	  0 [1][1][값1]
	  1 [1][1][값2]
	  .
	  .
	  n [n][m][ ]

	  위와 같은 경우 발생가능
	  */
	  //배열에 n까지 값을 저장하고 섞음으로 랜덤값 중복체크보다 시간 줄임

	  //0이 아닌 원소가 10%라고 가정하고 만든행렬이므로
	count = 0;
	for (m1 = 0; m1 < m; m1++) {
		Matrix[m1][2] = rand() % 10;
		//printf("[%d][3] = %d\n", m1, Matrix[m1][2]);
		if (Matrix[m1][2] == 0) {
			count++;
		}
	}
	//행열값
	//[][][0]
	//0값이 들어간 경우가 발생하는경우를 만들어줫으므로
	//값이 0인 (행,열)의 갯수를 셈
	Matrix[m-1][3] = count;
	return Matrix;
}


int** createMatrix(int m, int n){
	int** matrix;
	int m1;
	//10%이하여야하므로
	m1 = (m * n) / 10;

	matrix = (int**)malloc(sizeof(int*) * m1);
	for (int m2 = 0; m2 < (m1 - 1); m2++) {
		//행, 열, 값 3개
		matrix[m2] = (int*)malloc(sizeof(int) * 3);
	}
		//0갯수 저장
		matrix[(m1-1)] = (int*)malloc(sizeof(int) * 4);



	return matrix;
}

//m.c


#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
#include"h.h"

void main() {
	//mxn 행렬
	int m, n;
	int Msize;
	int** spares_matrix;
	float percent;

	printf("희소 행렬 크기 입력(m, n값): ");
	scanf("%d %d", &m, &n);

	printf("\n");

	Msize = (m * n / 10);
	//희소행렬의 0이 아닌값만 저장할 행렬
	//10%이하 여야함
	spares_matrix = createMatrix(m, n);
	spares_matrix = insertRand(spares_matrix, Msize);
	printf("    행    열    값\n");
	printf("------------------\n");
	printMatrix(spares_matrix, Msize);
	//희소 행열의 덧셈 결과 비교 출력, 0이 아닌 비율 출력
	SumMatrix(spares_matrix, Msize);
	showPercent(spares_matrix, Msize);

	printf("program End!\n(by32153682이창민)\n");
	printf("==================\n");
}

 

//makefile

app:m.o f.o
	gcc -o app m.o f.o

m.o: h.h m.c
	gcc -c m.c

f.o:h.h f.c
	gcc -c f.c

 

 

 

Problem 4: Infix 표현을 Postfix로 변환시키는 프로그램을 설계하고 구현하시오.

//toPostfix.h



//toPostfix by 이창민
/*
   *Stack
  중위표기수식만큼 크기 할당(괄호 빼고)
  (괄호 빼고 => 괄호 스택에 넣어 판단)

  *Infix_to_Postfix
  피연산자의 순서는 동일, 연산자들의 순서만다름
  즉, 연산자만 스택에 저장됨

  1. 피연산자를 만나면 그대로출력
  2. 연산자를 만나면 스택에 저장
  3. 스택에 있는 연산자보다 낮은순위의 연산자가 나오면 출력
  4. 왼쪽괄호는 연산자 우선순위가 가장 낮다고 판단
  5. 오른쪽 괄호를 만나면 출력(왼쪽괄호빼고)
 */

#include<stdio.h>

typedef struct{
	char* stack_data;
	int top;
}Stack;

void infix_to_postfix(Stack* s, char* exp);
void create(Stack* s, int exp_size);
int is_full(Stack* s, int exp_size);
void push(Stack* s, char data, int exp_size);
int is_empty(Stack* s);
char pop(Stack* s);
char peek(Stack* s);
void stack_free(Stack* s);
int size_nums(char* exp);
void checking(char* exp);
int order(char op);

//InfixToPostfix.c



#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"toPostfix.h"
int order(char op) {
	switch (op) {
	case '(': case')':
		return 0;
	case '+': case '-':
		return 1;
	case '*': case '/':
		return 2;
	default:
		return -1;
	}
}

void checking(char* exp) {
	char ch;
	char check;
	int i;
	int size = strlen(exp);
	Stack test;

	create(&test, size);

	for (i = 0; i < size; i++) {
		ch = exp[i];

		switch (ch) {
		case '(':
			push(&test, ch, size);
			break;
		case ')':
			check = pop(&test);
			if (check == 'f') {
				printf("error!! \")\" checking failed.\n");
				exit(1);
			}
			break;
		}
	}
}

void infix_to_postfix(Stack* s, char* exp) {
	char ch, op, result;
	int expSize;
	expSize = strlen(exp);
	for (int i = 0; i < expSize; i++) {
		ch = exp[i];
		switch (ch) {
		case '+': case '-': case '*': case '/': {
			//스택이 비어있지 않고 스택의 연산자보다 낮은 우선순위일때 pop
			if (!is_empty(s) && order(ch) <= order(peek(s))) {
				printf("%c", pop(s));
			}
			push(s, ch, expSize);//push ch 스택에
			break;
		}
		//왼쪽 괄호를 만나면 스택에 저장
		case '(': {
			push(s, ch, expSize);
			break;
		}
		//왼쪽 괄호가 나올때까지 출력
		case ')': {
			result = pop(s);
			while (result != '(') {
				printf("%c", result);
				result = pop(s);
			}
			break;
		}
		default: {
			printf("%c", ch);
			break; }

		}
	}
	while (!is_empty(s)) {
		printf("%c", pop(s));
	}
}

 

//size.c


#include<stdio.h>
#include<string.h>
#include"toPostfix.h"

int size_nums(char* exp) {
	int count = 0;
	int size = strlen(exp);
	for (int i = 0; i < size; i++) {
		char data = exp[i];

		switch (data) {
		case '(': case ')':
			count++;
			break;
		}
	}

	return size = size - count;

}

 

//stack.c



#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"toPostfix.h"
//스택 생성
void create(Stack* s, int exp_size) {
	s->stack_data = (char*)malloc(exp_size);
	s->top = -1;
}

//스택이 비었는지 확인
int is_empty(Stack* s) {
	return (s->top == -1);
}

int is_full(Stack* s, int exp_size) {
	return (s->top == (exp_size - 1));
}

void push(Stack* s, char data, int exp_size) {
	int top = s->top;
	if (is_full(s, exp_size)) {
		printf("stack is full!\n");
	}
	else {
		s->stack_data[++(s->top)] = data;
	}
}

char pop(Stack* s) {
	int top;
	if (is_empty(s)) {
		printf("stack is empty!\n");
		return 'f';
	}
	else {
		top = s->top;
		(s->top)--;
		return s->stack_data[top];
	}
}

char peek(Stack* s) {
	if (is_empty(s)) {
	}
	else {
		return s->stack_data[s->top];
	}
}

void stack_free(Stack* s) {
	free(s->stack_data);
}

 

//testing.c


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"toPostfix.h"

int main(int argc, char* argv[]){
	if(argc==1){
		printf("USEAGE : \"expression\" \"expression\"...\n");exit(1);
	}
	char* exp;
	int exp_size;
	Stack s;
	for (int i = 1; i < argc; i++) {
		exp = argv[i];
		printf("before : %s\n",exp);
		//괄호 이상여부 체크
		checking(exp);
		exp_size = size_nums(exp);
		create(&s, exp_size);
		printf("after : ");
		infix_to_postfix(&s, exp);
		printf("\n");
		stack_free(&s);
	}

	printf("\n");
	printf("Program End!\n");

	return 0;
}

 

//makefile

head = toPostfix.h
objects = testing.o InfixToPostfix.o size.o stack.o
files = InfixToPostfix.c size.c stack.c

app : $(head) $(objects)
	gcc -o app $(objects) 
testing.o : $(head) $(files)
	gcc -c testing.c
InfixToPostfix.o : $(head) InfixToPostfix.c
	gcc -c InfixToPostfix.c
size.o : $(head) size.c
	gcc -c size.c
stack.o : $(head) stack.c
	gcc -c stack.c