자료구조 및 알고리즘 수업을 듣는데 Linked list based stack을 배웠습니다. 근데 스택만 배우면 뭔가 아쉽더라구요. 그래서 Linked list based 스택을 이용해 간단한 프로그램을 만들어 보았습니다.
(이 글에서는 Linked list based stack을 이해했다고 가정하고 설명하겠습니다)
※이 코드는 잘 작성한 코드는 아닙니다!!! 좋은 코드를 원하셨다면 뒤로가는것을 추천...드립니다...※
스택을 이용한 대표적인 문제죠. Linked list based 스택을 이용한 괄호 짝 맞추기 문제입니다.
엑셀의 경우 함수를 넣을 때 괄호가 맞지 않으면 에러가 나게 하여 함수 구동 중에 예기치 못한 상황이 생기는것을 사전에 방지하고 있습니다.
이것을 C++로 간단하게 구현해 보겠습니다.
먼저 입력은 엑셀에서 함수를 넣듯이 입력됩니다. 공백을 포함한 모든 텍스트가 들어갑니다.
입력 예)
sum((A1:A7 = $H1) * (B1:B7)) //짝이 맞는 예
sum((A1:A7) * { (B1:B7} )) //쩍아 맞지 않은 예
출력은 공백을 지우고, 괄호의 짝이 맞는 지 확인하여 맞다면 "OK"를 출력하고 그 다음줄부터 공백을 제외한 텍스트를 작성합니다. 만약 괄호의 짝이 맞지 않다면 "Error!"를 출력하고 프로그램을 종료합니다.
출력 예)
※주의※
코드가 지저분합니다. 매우 지저분합니다. 앞으로 조금씩 가다듬도록 하겠습니다...
Linkedlist.h //링크드 리스트의 구현
#pragma once
#include <iostream>
using namespace std;
class Node {
public:
Node() { data = NULL; link = NULL; };
char data;
Node* link;
};
class Linkedlist {
public:
Linkedlist() { top = NULL; };
Node* top;
int isEmpty() {
return top == NULL;
};
void push(char received_data) {
Node* temp = new Node();
if (!temp) {
cout << "Stack OverFlow!" << endl;
exit(1);
}
temp->data = received_data;
temp->link = top;
top = temp;
};
void pop() {
Node* temp;
if (top == NULL) {
cout << "Stack UnderFlow!" << endl;
exit(2);
}
else {
temp = top;
top = top->link;
free(temp);
}
};
char peek() {
if (!isEmpty())
return top->data;
else {
cout << "Null pointer accessed!" << endl;
exit(3);
}
};
void cout_all(Node* temp) {
if (temp == NULL) { ; }
else {
cout_all(temp->link);
cout << temp->data;
}
}
};
LinkedList.cpp
#include <iostream>
#include <string>
#include "Linkedlist.h"
using namespace std;
int main() {
Linkedlist text, bracket;
string cindata = "";
int cin_index = 0;
bool error = false;
cout << "검사하려는 문장을 넣어주세요" << endl;
getline(cin, cindata);
while (cindata[cin_index] != NULL) {
if (cindata[cin_index] != ' ') {
switch (cindata[cin_index])
{
case ')':
if (bracket.peek() == '(') bracket.pop();
else error = true;
break;
case '}':
if (bracket.peek() == '{') bracket.pop();
else error = true;
break;
case ']':
if (bracket.peek() == '[') bracket.pop();
else error = true;
break;
default:
if (cindata[cin_index] == '(' || cindata[cin_index] == '{' || cindata[cin_index] == '[') {
bracket.push(cindata[cin_index]);
}
break;
}
text.push(cindata[cin_index]);
}
cin_index++;
}
if (bracket.isEmpty() == 0) {
error = true;
}
if (error) { cout << "Error!"; }
else { cout << "OK" << endl; text.cout_all(text.top); }
return 0;
}
코드 해석입니다.
1. cindata라는 스트링에 입력을 getline( )을 이용해 넣습니다.
2. string을 한 글자마다 확인하기 위해 while문을 이용합니다. cindata_index를 인덱스 변수로 두고 while문 안에서 하나씩 올려서 한 글자마다 다 확인하게 됩니다. 만약 인덱스를 하나 올렸는데 NULL값이라면 문장이 끝난것이므로 while문을 빠져나가도록 했습니다.
3. 확인한 글자가 공백이 아닌 경우에만 작동하도록 했습니다. 그리고 공백이 아니면 text라는 전체 문장을 담는 Linked list에 글자를 하나하나 push 해 주었습니다.
4. 여는 괄호의 경우, bracket이라는 Linked list에 괄호를 push 해 줍니다.
5. 닫는 괄호의 경우, bracket의 맨 꼭대기에 있는 텍스트가 자신과 맞는 종류의 여는 괄호면 정상적으로 pop을 해 줍니다. 만약 다른 종류이거나 아무것도 없다면 짝이 맞지 않은 것이니, error라는 변수를 true로 바꿉니다.
( { ( } <= 이와 같은 경우, 맨 마지막 } 를 처리할 때, 이전까지 bracket의 맨 꼭대기에는 ( 가 들어있습니다. if문에 의해 둘은 짝이 맞지 않다는 것을 확인할 수 있습니다.
6. 만약 while문을 나왔을 때 bracket에 글자가 남아있다면 이 또한 짝이 맞지 않은 것 입니다. 이 또한 에러를 true로 해줍니다.
( ( ( ) <= 와 같은 경우, while문을 나왔을 때 bracket에 ( ( 이 남아있어 에러가 나옵니다.
이를 출력하면 위에서 나온 것과 같습니다.
사실 1~3은 세팅이나 추가적인 작업이고, 주요 알고리즘은 4~6 입니다. stack의 push와 pop, peek을 이용해서 괄호의 짝이 맞는지 확인하는 알고리즘입니다.
블로그에 올리는 첫 글이 난이도가 있네요;; 다음엔 조금 기초적인 코딩을 정리해서 올려보도록 하겠습니다...! 감사합니다.