자료구조론 과제(1)

 

---

Array Stack 과제

ArrayStack.h

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H

#include <iostream>


using namespace std;

class StackEmpty {
public:
    StackEmpty(const string& err) { }
};

class StackFull {
public:
    StackFull(const string& err) { }
};


template <typename E>
class ArrayStack {
    enum { DEF_CAPACITY = 100 };		// default stack capacity
public:
    ArrayStack(int cap = DEF_CAPACITY);		// constructor from capacity
    int size() const;				// number of items in the stack
    bool empty() const;				// is the stack empty?
    const E& top() const throw(StackEmpty);	// get the top element
    void push(const E& e) throw(StackFull);	// push element onto stack
    void pop() throw(StackEmpty);		// pop the stack
    // ...housekeeping functions omitted
private:                                	// member data
    E* S;					// array of stack elements
    int capacity;				// stack capacity
    int t;					// index of the top of the stack
};


template <typename E> ArrayStack<E>::ArrayStack(int cap)
    : S(new E[cap]), capacity(cap), t(-1) { }	// constructor from capacity

template <typename E> int ArrayStack<E>::size() const
{
    return (t + 1);
}				// number of items in the stack

template <typename E> bool ArrayStack<E>::empty() const
{
    return (t < 0);
}				// is the stack empty?

template <typename E>				// return top of stack
const E& ArrayStack<E>::top() const throw(StackEmpty) {
    if (empty()) throw StackEmpty("Top of empty stack");
    return S[t];
}


template <typename E>				// push element onto the stack
void ArrayStack<E>::push(const E& e) throw(StackFull) {
    if (size() == capacity) throw StackFull("Push to full stack");
    S[++t] = e;
}

template <typename E>				// pop the stack
void ArrayStack<E>::pop() throw(StackEmpty) {
    if (empty()) throw StackEmpty("Pop from empty stack");
    --t;
}


#endif

 

ArrayStack.cpp

#include <iostream>
#include "ArrayStack.h"

using namespace std;


int main(void)
{
	ArrayStack<int> mystack;

	cout << mystack.size() << endl;

	mystack.push(1);
	mystack.push(2);

	cout << mystack.top() << endl;
	mystack.pop();

	cout << mystack.top() << endl;
	cout << mystack.size() << endl;

	return 0;
}

---

괄호매칭

우선 1번 소스코드는 괄호 매칭을 진행해보는 소스코드이다. 이 소스코드에서의 특징은 open bracket은 계속 stack에 넣어두고 close bracket은 stack의 top과 매칭을 하여 같은 형식의 set일 경우 top을 pop해주어 set가 있는 bracket은 stack에서 제거 해주는 것이다. 만약 모든 bracket이 제대로 matching되어 있어서 set가 딱 맞게 식에 존재한다면 stack에 남아있는 open bracket은 없을 것이다. 따라서 stack이 empty하면 bracket matching이 제대로 되되어있는 것으로 판단할 수 있고 stack이 empty하지 않다면 bracket이 제대로 matching되어있지 않다는 것으로 판단할 수 있다.

 

bracketmatching.cpp

#include <iostream>
#include "ArrayStack.h"
using namespace std;

//괄호 매칭함수
int bracketmatching(ArrayStack<char>& stack, string expression) {
	//범위기반 반복문
	for (const char& pair : expression) {
		//괄호 종류에 따라 분류
		switch (pair) {
		//open bracket의 경우
		case '(': case '{': case '[':
			stack.push(pair);	//stack에 문자를 입력
			break;	//반복문 종료

		//close bracket의 경우
		case ')': case '}': case ']':
			if (stack.empty()) {	//stack이 비어있으면
				cout << "false" << endl;	//false출력
				return 0;	//함수 종료
			}

			//stack이 비어있지 않다면
			char open_bracket = stack.top();	//open_bracket에 stack의 top을 입력
			stack.pop();		//해당 값은 pop
			if (open_bracket == '(' and pair != ')' or
				open_bracket == '{' and pair != '}' or
				open_bracket == '[' and pair != ']') {	//입력받은 close bracket과 stack에 있던 open bracket을 비교
				// (), {}, [] 세트가 아닌경우
				cout << "false" << endl;	//false출력
				return 0;	//함수 종료
			}
			break;	//반복문 종료
		}
	}
	//반복문 종료후
	if (!stack.empty()) {		//stack에 값이 남아있다면
		cout << "false" << endl;	//false출력
		return 0;
	}
	else {				//stack이 비어있다면
		cout << "true" << endl;		//true출력
		return 0;
	}
}

int main() {
	ArrayStack<char> bracket_stack;
	bracketmatching(bracket_stack, "(1+2)((3*4)){([( )])}");
	bracketmatching(bracket_stack, "((( )((1+2)){([(3+4 )])}");
	bracketmatching(bracket_stack, ")(( )){([(a+b )])}");
	bracketmatching(bracket_stack, "({[c/d])}");
	cout << endl << "이상훈 12211813" << endl;
	return 0;
}

---

Stock Span 알고리즘

2번 소스코드는 stock span 코드로 배열의 크기를 integer 변수 n에 담아두기 위해 vector STL을 사용하였다. Array의 크기를 구하는 sizeof()함수를 사용하지 못한 이유는 array를 함수의 인자로 받아올 경우 array는 pointer로 인식이 되기 때문에 sizeof(array)를 하면 언제나pointer변수의 default size인 8이 출력된다. 다른 부분은 강의노트의 pseudo 코드를 기반으로 작성하였기에 특별한 내용은 없고 주석에서 모두 설명이 되어있다. 다만 마지막에 각 날짜의 span값을 반복문을 이용하여 배열의 원소를 출력하여야했다.

 

stock_span.cpp

#include <iostream>
#include <vector>		//vector STL
#include "ArrayStack.h"
using namespace std;

//span을 computing하는 linear-time algorithm 함수
int computeSpans(vector<int> p) {
	ArrayStack<int> d;		//빈 stack d 선언
	int n = p.size();		//integer n에 vector의 길이 대입
	int h = 0;				//계산용 인자 h를 0으로 초기화
	int S[100];				//각 날짜의 span 값을 입력해둘 중분한 크기의 integer array S선언

	//for문을 이용하여 벡터의 사이즈n만큼 반복
	for (int i = 0; i < n; i++) {		
		int done = 0;					//done 명령어를 0으로 초기화

	//stack이 비어있거나 done명령어가 1로 바뀌지 않은 경우
		while (!(d.empty() == true or done == 1)) { 
	//stack의 top보다 조사하는 값이 더 크거나 같으면 stack에서 pop진행
			if (p[d.top()] <= p[i])		
				d.pop();
	//stack의 top보다 조사하는 값이 작으면 done을 1로 바꿔줌
			else
				done = 1;
		}
	//stack이 비어있으면 h를 -1로 설정
		if (d.empty() == true)
			h = -1;
	//이외의 경우 h를 stack d의 top으로 설정
		else
			h = d.top();

		S[i] = i - h;		//array S에 i-h를 통해 구한 span값 입력
		d.push(i);			//i값을 stack d에 push
	}

	//array S출력
	for (int i = 0; i < n; i++) {
		cout<< "Span" << i << " = " << S[i] << endl;
	};
	return 0;
}

//다양한 stock market 상황을 생성해두고 stockspan함수를 실행하는 main문
int main() {
	//다양한 stock market 상황
	vector<int> stock_value1 = { 6, 4, 1, 2, 1, 3, 5 };	//강의노트에 주어진 상황
	vector<int> stock_value2 = { 3, 2, 3, 5, 7, 8, 8, 7, 5, 3 };	//random1
	vector<int> stock_value3 = { 11, 10, 8, 6, 3, 4, 5, 4, 6, 8, 10, 12, 14 };	//random2

	cout << "Stock Span1" << endl;
	computeSpans(stock_value1);
	cout << endl << endl << endl << "Stock Span2" << endl;
	computeSpans(stock_value2);
	cout << endl << endl << endl << "Stock Span3" << endl;
	computeSpans(stock_value3);
	cout << endl << "이상훈 12211813" << endl;
	return 0;
}

---

Postfix_transform

3번 소스코드는 중위표기식을 후위 표기식으로 변환하는 postfix_transform함수에 관한 코드이다. 이 소스코드의 가장 큰 특징은 문자들은 바로 array에 입력하고 연산자들은 각각의 우선순위에 따라 stack에 담거나 stack의 top을 pop해주고 stack에 담아지는 경우로 나눠진다는 것이다. 이는 수업시간에 배운 내용과 강의노트의 내용을 기반으로 작성하였고 소스코드 내의 주석에서 line by line으로 상세하게 설명되어있다. 소스코드의 또다른 특징은 예외처리 입니다. Postfix_transform 함수 초반에 for문을 이용하여 음수가 존재하는 식인 경우 예외처리를 통해 error메세지가 출력되도록 하였다. 마지막 특징으로 연산자들의 유형이 존재했다. 1,2,3,4,5번 식들은 +-*/ 과 같은 우리가 평소에 이용하는 연산자들로 구성되어있는 식들이고 6,7번 식들은 && || !와 같은 논리 연산자들로 이루어져 있는 식들이었다. 그러나 두 유형 모두 연산자간의 우선순위만 제대로 설정을 해준다면 무리없이 코드를 완성할 수 있었다.

 

postfix_main.cpp

#include <iostream>
#include "ArrayStack.h"
using namespace std;

//후위표기식 변환 함수
string postfix_transform(ArrayStack<char>& oper_stack, string infix) {
	string ans;	//결과를 담아둘 ans 문자열 선언
	ArrayStack<char> checker_stack;
	//음수가 입력된 경우 error 처리
	for (const char& check : infix) {	//범위기반 반복문 사용
		if (check == '-') {				//음수일 가능성이 존재하는 -기호 조사
			if (checker_stack.empty()) {	//-가 문자열의 첫번째 문자인 경우 error 출력
				return "ERROR: can't control negative";
			}
			else if (checker_stack.top() == '-' or checker_stack.top() == '+' or
				checker_stack.top() == '*' or checker_stack.top() == '/') {
		//-가 연산자 바로 뒤에 출력되는 경우 즉 stack의 top이 연산자인 경우 error 출력
				return "ERROR: can't control negative";
			}
		}

		//-가 아닌 경우 stack에 계속 입력
		else {
			checker_stack.push(check);
		}
	}
	
	//범위기반 반복문 활용
	for (const char& oper : infix) {
	//char type의 oper를 상황에 따라 분류
		switch (oper) {	
		case '(':		//여는 괄호의 경우
			oper_stack.push('(');	//일단 stack에 넣음
			break;

		case ')':		//닫는 괄호
			while (!oper_stack.empty() and oper_stack.top() != '(') {
				//여는 괄호가 나올때까지 stack을 pop
				ans.push_back(oper_stack.top());	//문자열끝에 stack의 top을 입력
				oper_stack.pop();					//입력한 top은 pop해서 제거
			}
			oper_stack.pop();	//여는괄호는 stack에 넣지 않고 pop으로 제거
			break;
		
		//-------------------*,/,+,-류 연산(1,2,3,4,5번)에서 필요한 연산자)------------------
		case '*': case '/':		//우선순위가 높은 *과 /의 경우
			while (!oper_stack.empty() and (oper_stack.top() == '*' or oper_stack.top() == '/')) {
			//*, /을 만난 경우
				ans.push_back(oper_stack.top());	//ans문자열에 stack의 top을 입력
				oper_stack.pop();					//입력해준 top은 pop
			}
			oper_stack.push(oper);	//자신보다 낮는 우선순위의 연산자를 만나면 stack에 입력
			break;

		case '+': case '-':		//우선순위가 낮은 +와 -의 경우
			while (!oper_stack.empty() and oper_stack.top() != '(') {
			//top이 여는 괄호가 아닐경우
				ans.push_back(oper_stack.top());	//top을 문자열에 입력
				oper_stack.pop();		//그후 pop
			}
			oper_stack.push(oper);		//stack의 top에 여는 괄호가 있으면 연산자를 입력
			break;

			//----------------&&,//,!,<,>류 연산(6,7번)에서 필요한 연산자)-----------------
		case '!':
			while (!oper_stack.empty() and oper_stack.top() == '!') {
				//같은 !를 만난 경우
				ans.push_back(oper_stack.top());	//ans문자열에 stack의 top을 입력
				oper_stack.pop();					//입력해준 top은 pop
			}
			oper_stack.push(oper);	//자신보다 낮는 우선순위의 연산자를 만나면 stack에 입력
			break;

		case '&':		//우선순위가 높은 &&의 경우
			while (!oper_stack.empty() and oper_stack.top() == '!') {
				//자신보다 높은 우선순위의 연산자를 만난 경우
				ans.push_back(oper_stack.top());	//ans문자열에 stack의 top을 입력
				oper_stack.pop();					//입력해준 top은 pop
			}
			oper_stack.push(oper);	//자신보다 낮는 우선순위의 연산자 또는 자신을 만나면 stack에 입력
			break;

		case '|':		//우선순위가 낮은 ||의 경우
			while (!oper_stack.empty() and 
				(oper_stack.top() == '!' or oper_stack.top() == '&')) {
				//자신보다 높은 우선순위의 연산자를 만난 경우
				ans.push_back(oper_stack.top());	//ans문자열에 stack의 top을 입력
				oper_stack.pop();					//입력해준 top은 pop
			}
			oper_stack.push(oper);	//자신보다 낮는 우선순위의 연산자 또는 자신을 만나면 stack에 입력
			break;

		case '<': case '>':		//우선순위가 가장낮은 <와 >의 경우
			while (!oper_stack.empty() and oper_stack.top() != '(') {
				//top이 여는 괄호가 아닐경우
				ans.push_back(oper_stack.top());	//top을 문자열에 입력
				oper_stack.pop();		//그후 pop
			}
			oper_stack.push(oper);		//stack의 top에 여는 괄호가 있으면 연산자를 입력
			break;




		default:	//연산자가 아닌 경우
			ans.push_back(oper);	//문자들은 문자열에 바로 입력
		}
	}

	while (!oper_stack.empty()) {		//stack에 값이 존재하는 경우
		ans.push_back(oper_stack.top());	//문자열에 top을 입력하고
		oper_stack.pop();					//pop해줌
	}

	return ans;		//재구성한 식을 return해줌
}


int main() {
	ArrayStack<char> oper_stack;
	cout << postfix_transform(oper_stack, "A*B*C") << endl;
	cout << postfix_transform(oper_stack, "((A+(B*C))-(D/E))") << endl;
	cout << postfix_transform(oper_stack, "-A+B-C+D") << endl;
	cout << postfix_transform(oper_stack, "A*-B+C") << endl;
	cout << postfix_transform(oper_stack, "(A+B)*D+E/(F+A*D)+C") << endl;
	cout << postfix_transform(oper_stack, "A&&B||C||!(E>F)") << endl;
	cout << postfix_transform(oper_stack, "!(A&&!((B<C)||(C>D)))||(C<E)") << endl;
	cout << endl << "이상훈 12211813" << endl;
	return 0;
}

---