ArrayStack(1)

---

괄호 매칭

ArrayStack을 이용하여 괄호 매칭 시스템을 만들어보았다.

//ArrayStack Header Source Code

#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

#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
            //입력받은 close bracket과 stack에 있던 open bracket을 비교
			if (open_bracket == '(' and pair != ')' or
				open_bracket == '{' and pair != '}' or
				open_bracket == '[' and pair != ']') {	
				// (), {}, [] 세트가 아닌경우
				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;
}

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되어있지 않다는 것으로 판단할 수 있다.

---