[자료구조 실습] 괄호매칭

괄호매칭

배열을 이용한 스택을 활용하여 괄호가 잘 매칭 되었는지 확인 하는 프로그램이다.

 

어떤 식이 주어졌을 때 괄호 매칭이 ( ), { }, [ ] 과 같이 정상적이게 매칭 되었는지 확인하기 위해서는 다음과 같은 조건이 성립해야 한다.

조건1) open, close 괄호의 개수가 같아야 한다. 조건2) 괄호의 종류(),{},[] 중 같은 종류의 괄호는 open 괄호가 먼저 나와야 한다. 조건3) 종류가 다른 괄호가 교차되면 안된다. ex) ( { ) }

 

위와 같은 조건을 스택을 이용하여 만족하기 위해 조건을 다음과 같이 재해석 하였다.

open 괄호는 스택에 push(), close 괄호를 만나면 스택의 top을 pop() 한다.   조건1) 괄호 검사가 끝났을 때 스택이 empty()한 경우는 open, close 괄호의 개수가 같음을 의미한다.   조건2) 같은 종류의 괄호에서, 만약 close 괄호가 나오는 경우는 두가지 case가 있다. case1 : 앞서 다른 종류의 open괄호가 있어 stack이 !empty()한 경우. - stack의 top과 close괄호가 짝꿍이 아니므로 pop을 하면 안된다. case2 : 앞서 다른 종류의 open괄호가 없으며 stack이 empty한 경우. - case2의 경우는 empty하여 pop 할 수 없다.   조건3) 종류가 같을 시에만 top을 pop한다. ( { ) }를 예로 하면 ‘ ( ‘, ‘ { ‘가 push()되고 ‘ ) ‘는 현재 스택의 top()=’ { ‘의 짝꿍이 아니므로 넘어간다. ‘ } ‘를 만나면 top=’ { ‘가 pop() 되고 스택에는 ‘ ( ‘만 남게 될 것이다. 따라서 괄호 검사가 끝났을 때 스택이 !empty() 한 경우 괄호 검사 실패를 출력한다.

 다음 조건들을 만족하는 main.cpp 코드는 다음과 같다.

main.cpp

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

int main() {
    ArrayStack<char> st; //괄호 식을 배열의 스택으로 받을 거기때문에 char 형태의 ArrayStack<char> st를 정의한다.
    string input; //괄호식을 입력받기 위한 변수 선언
    int n = 1; //n은 아래 반복문(괄호식)의 counter
 

    cout << "과제 1번째 괄호쌍 입력 (종료를 원하시면 out 입력 ):  ";

    while (cin >> input) { //괄호쌍을 계속 입력받는 while문.

        if (input == "out") { //while문을 멈추는 제어 구문. input에 out을 입력 시 while문이 끝난다.
            break;
        }
       
        st.Stackinit(&st); // 스택을 빈 상태로 초기화.        
        for (int i = 0; i < input.length(); i++) { //for문은  intput의 길이 만큼 반복한다.
            if (input[i] == '[' || input[i] == '{' || input[i] == '(') { // [,{,(를 만나면 이들을 스택에 넣는다.
                st.push(input[i]);
                cout << "stack에 push : " << input[i] << endl;

            }

            else if (input[i] == ']' || input[i] == '}' || input[i] == ')') {
                if (st.empty()) {
                    cout << "조건 2-2 위반.. \n 괄호검사 실패\n"; //닫히는 괄호를 만났을때 스택이 빈 경우, 스택에 열리는 괄호가 없는 경우이다. 즉 짝꿍이 없는 상태이다.
                    break; //괄호검사 실패.
                }

                //스택이 비어있지 않는경우
                else if (input[i] == ']' && st.top() == '[') {  //input[i]가 ]이고 스택의 top이 [이면 top [를 pop 한다.
                    cout << "stack의 top을 pop : " <<st.top()<< endl;
                    st.pop();

                }
                else if (input[i] == '}' && st.top() == '{') {//input[i]가 }이고 스택의 top이 {이면 top {를 pop 한다.
                    cout << "stack의 top을 pop :  " << st.top() << endl;
                    st.pop();
                }
                else if (input[i] == ')' && st.top() == '(') {//input[i]가 )이고 스택의 top이 (이면 top (를 pop 한다.
                    cout << "stack의 top을 pop : " << st.top() <<  endl;
                    st.pop();

                }
            }
       
            if (i == input.length()-1) { //i는 0부터 시작하기 때문에 input.length()에 -1을 하였고 "만약 괄호식 끝까지 for루프가 돌았을 때" 를 의미한다.
                if (st.empty()) { //괄호식 끝까지 루프가 돌았으며 스택이 빈 경우 괄호 검사가 성공 한것이다.
                    cout << "\n !! 괄호검사 성공!!  " << endl;
                }
                else { //괄호식 끝까지 루프가 돌았는데 스택이 비어있지 않는 경우는 open 괄호가 close 짝꿍을 못만난 경우로 괄호 검사에 실패한 경우이다.
                    cout << "\n조건2-1 or 조건 3 위반.. Stack is not empty.." << endl;
                }
            }
            
        }
        if (!st.empty()) { //괄호검사 실패 출력
            
            cout << "조건1 위반..괄호 검사 실패 . . . 식을 확인하세요 "  << endl;
        }

        n++; 
        cout <<"\n과제 "<<n<<" 번째 괄호쌍을 입력 : " << endl;
    }

 

그리고 위의 스택 배열을 만들기 위한 ArrayStack.h의 코드는 다음과 같으며, 일전의 게시물에서 만든것과 동일하나 그것에 스택을 초기화하는 함수를 하나 더 추가하였다.

Arraystack_h

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H //헤더파일이 여러번 include 되어도 중복 선언되지 않게 하기 위해..

#include <iostream>
using namespace std; //<iostream> 라이브러리 사용

class StackEmpty { //스택이 비었는지 확인하는 클래스.
    //throw(StackEmpty)와 같이 사용할 것이다.
public:
    StackEmpty(const string& err) { } //StackEmpty 함수는 string 변수의 주소를 가져온다.
};

class StackFull { //스택이 꽉 찼는지 확인하기 위한 class
public:
    StackFull(const string& err) { } //StackFull 함수를 사용하며 인자로 string 인자의 주소를 받는다.
};


template <typename E>
class ArrayStack { //클래스 ArrayStack
    enum {     //enum은 모든 값을 기호 상수로 정의되는 자료형이다. 

        DEF_CAPACITY = 100  //스택의 기본 용량을 100으로 정의한다.
    };		

public:
    ArrayStack(int cap = DEF_CAPACITY);	//생성자로 int cap을 매개 변수로 받으며 DEF_CAPACITY로 초기화 한다.
    void Stackinit(ArrayStack* stack);

    int size() const;				// 스택의 항목수. 
    bool empty() const;				// 함수가 비었는지 bool을 통해 알 수 있음.
    const E& top() const throw(StackEmpty);	// top의 요소를 알 수 있는 함수.
    //E는 template로 정의한 것으로 top이 int면 int로, double이면 double로 자료형을 정의할 것이다.
    //top의 주소를 받으며, throw(StackEmpty)을 하여 스택이 비었나 안비었나 확인한다.

    void push(const E& e) throw(StackFull);	// 스택에 요소를 push하는 함수.
    //스택이 꽉 찼을 경우를 알기 위해 throw(StackFull)을 해야한다.

    void pop() throw(StackEmpty);		// pop.
    //함수가 비어있을 경우에는 pop을 못하므로 throw(StackEmpty)를 통해 함수가 비었는지 확인한다.
    // ...하우스 키핑 기능 생략

    int cheking(char* expression);

private:                                	// priave 접근지정자. 외부에서 접근이 불가능하다.
    E* S;					// 템플릿 E는 S에 들어오는 자료형을 자료형으로 쓸 것이며 E* S는  S를 포인터 선언한다.
    //=스택 원소들의 배열

    int capacity;				// 스택의 용량
    int t;					// 스택의 맨위인 top 정의
};


template <typename E>  //template E 정의
ArrayStack<E>::ArrayStack(int cap) 
    : S(new E[cap]), capacity(cap), t(-1) { }	//생성자는 디폴트 용량을 받는다.
//top을 -1로 두는 것은 Stack이 공간은 있지만 원소는 없는 상태를 말한다.

template <typename E>
void ArrayStack<E>::Stackinit(ArrayStack* stack) {
   t= -1;
}

template <typename E>//template E 정의 
int ArrayStack<E>::size() const
{ 
    return (t + 1); //t는 스택 맨 위의 top으로 스택은 0~n-1개로 표현하기에 size는 top+1을 해줘야한다.
}	//=스택에 있는 원소의 수

template <typename E> 
bool ArrayStack<E>::empty() const 
{
    return (t < 0); //top이 0보다 작음을 리턴한다.
}				

template <typename E>				
const E& ArrayStack<E>::top() const throw(StackEmpty) { //top의 주소를 받으며 스택이 비었음을 알기 위해 throw(StackEmpty)를 한다.
    if (empty()) throw StackEmpty("Top of empty stack"); //만약 스택이 비었다면 StackEmpty("Top of emty stack")을 throw한다.
    return S[t]; //= 배열의 top을 리턴 
}


template <typename E>				
void ArrayStack<E>::push(const E& e) throw(StackFull) { //스택에 요소 e를 push한다. e의 주소를 인자로 받으며 스택이 꽉찼는지 알기 위해 throw(StackFull_을 한다.
    if (size() == capacity) throw StackFull("Push to full stack"); //만약 사이즈가 용량과 같다면, StackFull("Push to full stack")을 throw 한다.
    S[++t] = e;//=++top를 e로 한다.
}

template <typename E>				
void ArrayStack<E>::pop() throw(StackEmpty) { //스택에 맨 위를 pop한다. 스택이 비어있으면 안되므로 throw(StackEmpty)를 한다.
    if (empty()) throw StackEmpty("Pop from empty stack"); //만약 스택이 비었다면 throw StackEmpty("Pop from empty stack")
    --t; //t를 빼냄.
}


#endif