Stack을 이용한 알고리즘 문제-편집기(Editor)

🎈1.문제설명

-한줄로 된 간단한 편집기(Editor)를 구현하려고 한다

-이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 500,000글자꺼지 입력할 수 있다

-이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장 맨뒤(마지막 문자의 오른쪽),

문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치 할 수 있다

-즉 길이가 len 인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 len+1가지 경우가 있다.

---

* 편집기가 지원하는 명령어 *

L: 커서를 왼쪽으로 한 칸 옮김(커서가 문장의 맨 앞이면 무시됨)

D: 커서를 오른쪽으로 한 칸 옮김(커서가 문장의 맨 뒤이면 무시됨)

B: 커서 왼쪽에 있는 문자를 삭제함(커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한것처럼 나타나지만 실제로 커서의 오른쪽에 있던 문자는 그대로임 p$ $라는 문자를 커 서 앞쪽에 추가함 - 커서는 $의 오른쪽에 위치함

초기 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을때, 모든 명령어를 수행하고 난 후 편집기에 압력되어 있는 문자열을 구하는 프로그램을 작성한다.

단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 가정한다.

---

* 데이터 파일의 내용 *

-첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이문자열은 영어 소문자로만 이루어져 있으며,길이는 100,000을 넘지 않는다.

-둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1<=N<=500,00)이 주어진다.

-셋째 줄부터 N개의 줄에 거쳐 입력할 명령어가 순서대로 주어진다.

-명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

-L: 커서 왼쪽으로 이동

-D: 커서 오른쪽으로 이동

-B :커서 왼쪽 문자 삭제

-P$:커서 앞에 문자 추가

🎆2. 출력 화면

🎇3.코드+주석

(1) Funtion.cpp

#include "17강 listStack.h"
#include <stdio.h>
#include <malloc.h>
/*--------------------------------------------------------------------------------------
Function name	: createStack - 링크드리스트로 관리되는 스택 생성 함수
Parameters		: sp - 스택관리 구조체의 주소
Returns			: 성공 - TRUE / 실패 - FALSE
--------------------------------------------------------------------------------------*/
BOOL createStack(Stack *sp)
{
	if (sp == NULL) {  /* sp포인터 NULL check*/
		return FALSE;
	}
	sp->head = (Snode *)calloc(1, sizeof(Snode)); /* 헤드 노드 생성	*/
	if (sp->head == NULL) {
		return FALSE;
	}
	sp->tail = (Snode *)calloc(1, sizeof(Snode)); /* 테일 노드 생성 */
	if (sp->tail == NULL) {
		free(sp->head);
		return FALSE;
	}
	/* 헤드노드가 테일노드를, 테일노드가 테일노드를 가리키게 함 */
	sp->head->next = sp->tail;
	sp->tail->next = sp->tail;
	return TRUE;
}
/*--------------------------------------------------------------------------------------
Function name	: isStackEmpty() - 스택이 비어있는가 검사
Parameters		: sp - 스택관리 구조체의 주소
Returns			: 완전히 비어있으면 TRUE 리턴, 비어있지 않으면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL isStackEmpty(const Stack *sp)
{
	if (sp == NULL) {  /* sp포인터 NULL check*/
		return FALSE;
	}

	if (sp->head->next == sp->tail)
		return TRUE;
	else
		return FALSE;
}
/*--------------------------------------------------------------------------------------
Function name	: push() - 스택에 데이터 하나를 저장함
Parameters		: sp - 스택관리 구조체의 주소
				  pushData  - 스택에 저장할 데이터
Returns			: 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL push(Stack *sp, char pushData)
{
	Snode *cur;			/* 작업용 Snode 포인터 선언 */
	if (sp == NULL) {	/* sp포인터 NULL check*/
		return FALSE;
	}

	cur = (Snode *)calloc(1, sizeof(Snode));	/* 새로운 노드 생성 */
	if (cur == NULL) {		/* 메모리 할당 실패하면 push실패 */
		return FALSE;
	}
	else {					/* 새 노드를 head node 바로 뒤에 노드 추가 */
		cur->data = pushData;
		cur->next = sp->head->next;
		sp->head->next = cur;
		//cur->data = pushData; /* 새 노드의 데이터 영역에 데이터 복사 */
		return TRUE;
	}
}
/*--------------------------------------------------------------------------------------
Function name	: pop() - 스택에서 데이터 하나를 꺼냄
Parameters		: sp - 스택관리 구조체의 주소
popData - 꺼낸 데이터를 저장할 기억공간의 주소
Returns			: 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL pop(Stack *sp, char *popData)
{
	Snode *cur;			/* 작업용 Snode 포인터 선언 */
	if (sp == NULL) {  /* sp포인터 NULL check*/
		return FALSE;
	}

	if (isStackEmpty(sp) == TRUE) {	/* stack이 비어있으면 pop실패 */
		return FALSE;
	}
	else {		/* head node 뒤에서 데이터를 꺼낸 후 데이터 노드 삭제 */
		*popData = sp->head->next->data;
		cur = sp->head->next;
		sp->head->next = sp->head->next->next;
		free(cur);
		return TRUE;
	}
}
/*--------------------------------------------------------------------------------------
Function name	: printStack - 스택의 모든 데이터 출력(pop하면 나오는 순서대로 출력)
Parameters		: sp - 스택관리 구조체의 주소
Returns			: 없음
--------------------------------------------------------------------------------------*/
void printStack(const Stack *sp)
{
	Snode *cur;			/* 작업용 Snode 포인터 선언 */
	if (sp == NULL) {	/* sp포인터 NULL check*/
		return;
	}

	if (isStackEmpty(sp) == TRUE)
	{
		printf("Stack이 비어있습니다!!\n");
		return;
	}
	cur = sp->head->next;
	while (cur != sp->tail)
	{
		printf("%c", cur->data);
		cur = cur->next;
	}
	printf("\n");
	return;
}
/*--------------------------------------------------------------------------------------
Function name	: destroyStack() - 스택 소멸 함수
Parameters		: sp - 스택관리 구조체의 주소
Returns			: 없음
--------------------------------------------------------------------------------------*/
void destroyStack(Stack *sp)
{
	Snode *cur;			/* 작업용 Snode 포인터 선언 */
	if (sp == NULL) {	/* sp포인터 NULL check*/
		return;
	}
	/* 데이터 첫 노드부터 맨 뒤의 노드까지 모두 삭제 */
	while (sp->head->next != sp->tail)
	{
		cur = sp->head->next;
		sp->head->next = sp->head->next->next;
		free(cur);
	}
	free(sp->head);	/* 헤드노드 삭제 */
	free(sp->tail);	/* 테일노드 삭제 */
	sp->head = sp->tail = NULL; /* head, tail 포인터를 NULL로 초기화 */

	return;
}

(2) main.cpp

#define _CRT_SECURE_NO_WARNINGS
#include "17강 listStack.h"
#include <stdio.h>

int main()
{
	Stack lstk, rstk;     /* 왼쪽, 오른쪽 스택 생성*/
	FILE *fp;
	char ch;
	int i;
	int cmdCnt;  /* 명령어 개수 저장 변수 */

	createStack(&lstk); /* 스택초기화*/
	createStack(&rstk); /* 스택초기화*/

	fp = fopen("c:\\Temp\\editor1.txt", "rt");
	if (fp == NULL) {
		printf("파일 오픈 에러!!\n");
		getchar();
		return 1;
	}

	while ((ch = fgetc(fp)) != '\n')
		push(&lstk, ch);
	fscanf(fp, "%d", &cmdCnt);

	for (i = 0; i < cmdCnt; ++i) {
		fscanf(fp, "%c", &ch);
		switch(ch)
		{
		case 'p':
			fscanf(fp, "%c", &ch);
			push(&lstk, ch);
			break;
		case 'L':
			if (pop(&lstk, &ch))
			push(&rstk, ch);
			break;
		case 'D':
			if (pop(&rstk, &ch))
				push(&lstk, ch);
			break;
		case'B':
			pop(&lstk, &ch);
			break;
	}

}
	while (pop(&lstk, &ch))
		push(&rstk, ch);
	printStack(&rstk);

	destroyStack(&lstk);
	destroyStack(&rstk);

	fclose(fp);
	getchar();
	return 0;
}

(3)header.h

#pragma once
enum BOOL { FALSE, TRUE };

typedef struct _stacknode Snode;

struct _stacknode
{
	char data;		/* char 데이터 영역 */
	Snode *next;	/* 다음 노드를 가리키는 포인터 영역 */
};

typedef struct _stack	/* stack 관리 구조체 */
{
	Snode *head;	/* head pointer (head node 가리킴) */
	Snode *tail;	/* tail pointer (tail node 가리킴) */
}Stack;

BOOL createStack(Stack *sp);		/* 링크드리스트로 관리되는 스택 생성 함수 */
BOOL isStackEmpty(const Stack *sp);		/* 스택이 완전히 비어있는가 검사 */
BOOL push(Stack *sp, char pushData);	/* 스택에 데이터 저장하는 함수 */
BOOL pop(Stack *sp, char *popData);	/* 스택에서 데이터를 꺼내는 함수 */
void printStack(const Stack*sp);		/* 스택 내의 모든 데이터를 출력하는 함수 */
void destroyStack(Stack *sp);			/* 스택 메모리 해제 함수 */

✨3.느낌점

이번 시간에 배운 stack을 이용하여 마지막으로 stack을 이용한 알고리즘 문제를 풀어봤다. 문제는 편집기를 만드는 프로그램을 주어진 조건에 따라 만드는 형식으로 스택의 헤드포인터와 테일 포인터와 노드를 이용하여, 스택을 만들고 주어진 편집기 명령문을 push, pop을 제대로 작동시키면 기본적인 편집기를 만들 수 있었다. 비록 문제를 이해하고 푸는데 시간이 좀 걸리기 했지만 인터넷과 나머지 자료들을 찾아보면서 프로그램을 수행 할 수 있었다. 앞으로 알고리즘 문제를 푸는 시간을 단축시켜 코드의 효율성과 단축성을 잘 생각하고 만들어야겠다는 생각이 들었다/