본문 바로가기
프로그래밍/자료구조

스택을 이용해 괄호 검사, 문자열 역순 출력

부산형 2019. 10. 14. 17:10

ArrayStack 괄호검사

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_SIZE 10
#define ERROR_CODE 255
#define STRING_SIZE 20

//데이터 정의
typedef char element;

typedef struct {
	element stack[STACK_SIZE];
	int top;
} ArrayStack;


//연산 정의
ArrayStack* createStack() {
	ArrayStack* s;
	s = (ArrayStack*)malloc(sizeof(ArrayStack));
	s->top = -1;

	return s;
}

int isEmpty(ArrayStack* s) {
	if (s->top == -1) return 1;
	else return 0;
}

int isFull(ArrayStack * s) {
	if (s->top >= STACK_SIZE - 1) return 1;
	else return 0;
}

int push(ArrayStack * s, element data) {
	if (isFull(s)) {
		printf("stack overflow\n");
		return ERROR_CODE;
	}

	s->top++;
	s->stack[s->top] = data;
	return 1;
}

element pop(ArrayStack * s) {
	element temp;

	if (isEmpty(s)) {
		printf("stack underflow\n");
		return ERROR_CODE;
	}

	temp = s->stack[s->top];
	s->top--;
	return temp;
	//return s->stack[s->top--];
}

element peek(ArrayStack * s) {
	if (isEmpty(s)) {
		printf("stack is empty\n");
		return ERROR_CODE;
	}

	return s->stack[s->top];
}

void printStack(ArrayStack * s) {
	int i;
	for (i = 0; i <= s->top; i++) {
		printf("%d\t", s->stack[i]);
	}
	printf("\n");
}

int checker(char s[]) {
	ArrayStack* stack;
	int i;
	char c, old;
	int len = strlen(s);

	stack = (ArrayStack*)createStack();

	for (i = 0; i < len; i++) {
		c = s[i];

		switch (c) {
		case '(':
		case '{':
		case '[':
			push(stack, c);
			break;
		case')':
			old = pop(stack);
			if (old != '(') return 0;
			break;
		case'}':
			old = pop(stack);
			if (old != '{') return 0;
			break;
		case']':
			old = pop(stack);
			if (old != '[') return 0;
			break;
		default:
			;
		}
	}

	if (!isEmpty(stack)) return 0;

	return 1;
}


int main() {

	char s[STRING_SIZE];

	printf("문자열 입력");
	scanf("%s", s);

	if (checker(s)) printf("괄호의 쌍이 맞습니다. \n");
	else printf("괄호의 쌍이 맞지 않습니다. \n");


	return 0;
}

LinkedStack 괄호 검사

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define STACK_ERROR 255
#define STRING_SIZE 20

typedef char element;

typedef struct stacknode {
	element data;
	struct stacknode* link;
}StackNode;

typedef struct {
	int numOfNode;
	StackNode* top;
}LinkedStack;

LinkedStack* createStack() {
	LinkedStack* s = (LinkedStack*)malloc(sizeof(LinkedStack));
	s->numOfNode = 0;
	s->top = NULL;
	return s;
}

int isEmpty(LinkedStack* s) {
	if (s->top == NULL) return 1;
	else return 0;
}

int push(LinkedStack * s, element data) {
	StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
	if (newNode == NULL) {
		printf("stack overflow\n");
		return STACK_ERROR;
	}
	newNode->data = data;

	newNode->link = s->top;
	s->top = newNode;
	s->numOfNode++;
	return 1;
}

element pop(LinkedStack * s) {
	StackNode* temp;
	element data;
	temp = s->top;
	if (isEmpty(s)) {
		printf("stack underflow\n");
		return STACK_ERROR;
	}
	s->top = temp->link;
	s->numOfNode--;

	data = temp->data;
	free(temp);
	return data;
}

element peek(LinkedStack * s) {
	if (isEmpty(s)) {
		printf("Stack is Empty\n");
		return STACK_ERROR;
	}
	return s->top->data;
}

void printStack(LinkedStack * s) {
	StackNode* temp;
	temp = s->top;
	while (temp != NULL) {
		printf("%c\n", temp->data);
		temp = temp->link;
	}
	printf("\n");
}

int checker(LinkedStack* stack, char s[]) {
	int i;
	char c, old;
	int len = strlen(s);
	for (i = 0; i < len; i++) {
		c = s[i];
		switch (c) {
		case '(':
		case '{':
		case '[':
			push(stack, c);
			break;
		case')':
			old = pop(stack);
			if (old != '(') return 0;
			break;
		case'}':
			old = pop(stack);
			if (old != '{') return 0;
			break;
		case']':
			old = pop(stack);
			if (old != '[') return 0;
			break;
		default:
			;
		}
	}
	if (!isEmpty(stack)) return 0;

	return 1;
}

int main() {
	LinkedStack* s1;
	s1 = createStack();

	char s[STRING_SIZE];

	printf("문자열 입력");
	scanf("%s", s);
	if (checker(s1,s)) printf("괄호의 쌍이 맞습니다. \n");
	else printf("괄호의 쌍이 맞지 않습니다. \n");
	return 0;
}

 

ArrayStack 문자열 역순 출력

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_SIZE 20
#define ERROR_CODE 250
#define STRING_SIZE 20

typedef char element;

//스택 구조체
typedef struct {
	element stack[STACK_SIZE];
	int top;
}ArrayStack;

//stack만들기
ArrayStack* createStack() {
	ArrayStack* s = (ArrayStack*)malloc(sizeof(ArrayStack));
	s->top = -1;
	return s;
}

//스택이 비었는지 검사
int isEmpty(ArrayStack* s) {
	if (s->top == -1)return 1;
	else return 0;
}

//스택이 가득 찼는지 검사
int isFull(ArrayStack * s) {
	if (s->top >= STACK_SIZE - 1) return 1;
	else return 0;
}

//push
int push(ArrayStack * s, element data) {
	if (isFull(s)) {
		printf("stack overflow\n");
		return ERROR_CODE;
	}
	s->top++;
	s->stack[s->top] = data;
	return 1;
}

//pop
element pop(ArrayStack * s) {
	element temp;
	if (isEmpty(s)) {
		printf("stack underflow\n");
		return ERROR_CODE;
	}
	temp = s->stack[s->top];
	s->top--;
	return temp;
	//return s->stack[s->top--];
}

//peek
element peek(ArrayStack * s) {
	if (isEmpty(s)) {
		printf("stack is Empty\n");
		return ERROR_CODE;
	}
	return s->stack[s->top];
}

void printStack(ArrayStack * s) {
	int index;
	if (isEmpty(s)) return;
	index = s->top;
	while (index != -1) {
		printf("%d\n", s->stack[index--]);
	}
}

void reverseString(ArrayStack* s,char str[]) {
	int len = strlen(str);
	char c;
	
	for (int i = 0; i < len; i++) {
		c = str[i];
		push(s, c);
	}
	while (s->top!=-1){
		printf("%c", pop(s));
	}
	printf("\n");
}

int main() {
	ArrayStack* s1;
	s1 = createStack();
	char str[STRING_SIZE];
	printf("문자열 입력:");
	scanf("%s", str);
	reverseString(s1, str);
	return 0;
}

 

LinkedStack 문자열 역순 출력

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_ERROR 255
#define STRING_SIZE 20

typedef char element;

typedef struct stacknode {
	element data;
	struct stacknode* link;
}StackNode;

typedef struct {
	int numOfNode;
	StackNode* top;
}LinkedStack;

LinkedStack* createStack() {
	LinkedStack* s = (LinkedStack*)malloc(sizeof(LinkedStack));
	s->numOfNode = 0;
	s->top = NULL;
	return s;
}

int isEmpty(LinkedStack* s) {
	if (s->top == NULL) return 1;
	else return 0;
}

int push(LinkedStack * s, element data) {
	StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
	if (newNode == NULL) {
		printf("stack overflow\n");
		return STACK_ERROR;
	}
	newNode->data = data;

	newNode->link = s->top;
	s->top = newNode;
	s->numOfNode++;
	return 1;
}

element pop(LinkedStack * s) {
	StackNode* temp;
	element data;
	temp = s->top;
	if (isEmpty(s)) {
		printf("stack underflow\n");
		return STACK_ERROR;
	}
	s->top = temp->link;
	s->numOfNode--;

	data = temp->data;
	free(temp);
	return data;
}

element peek(LinkedStack * s) {
	if (isEmpty(s)) {
		printf("Stack is Empty\n");
		return STACK_ERROR;
	}
	return s->top->data;
}

void printStack(LinkedStack * s) {
	StackNode* temp;
	temp = s->top;
	while (temp != NULL) {
		printf("%d\n", temp->data);
		temp = temp->link;
	}
	printf("\n");
}

void reverseString(LinkedStack*s, char str[]) {
	int len = strlen(str);
	char c;

	for (int i = 0; i < len; i++) {
		c = str[i];
		push(s, c);
	}
	while (!isEmpty(s)) {
		printf("%c", pop(s));
	}
	printf("\n");
}

int main() {
	LinkedStack* s1;
	s1 = createStack();
	char str[STRING_SIZE];
	printf("문자열 입력:");
	scanf("%s", str);
	reverseString(s1, str);
	return 0;
}

'프로그래밍 > 자료구조' 카테고리의 다른 글

배열 순차리스트  (0) 2019.11.04
연결리스트 큐(Queue) 구현  (0) 2019.10.18
배열을 이용한 큐(Queue)  (0) 2019.10.17
연결리스트로 Stack 구현  (0) 2019.10.11
배열로 Stack 구현  (0) 2019.10.11

'프로그래밍/자료구조' Related Articles

티스토리툴바