11일차

스택의 응용 : 올바른 괄호 검사

∙ 올바른 괄호 검사

- 괄호만으로 이루어진 문자열이 주어질 때, 괄호의 종류별로 쌍이 제대로 되어 있는지를 검사하기

- 괄호의 종류 : [ ] (대괄호, brackets), { } (중괄호, braces), ( ) (소괄호, parentheses)

- 올바른 괄호의 조건 

> 괄호의 종류별로 여는 괄호와 닫는 괄호의 개수가 같아야 한다.

> 같은 종류의 괄호에서 여는 괄호가 닫는 괄호보다 먼저 나타나야 한다.

> 마지막 여는 괄호와 쌍이 되는 닫는 괄호가 먼저 나타나야 한다.

 

∙ 올바른 괄호 검사 알고리즘

- 문자열의 각 문자를 차례대로 검사

> 여는 괄호 (, {, [ 를 만나면 스택에 push

> 닫는 괄호 ), }, ] 를 만나면 

         > 스택이 비어 있으면 false 반환

         > 스택의 top에 있는 문자가 현재 닫는 괄호와 쌍을 이루는 여는 괄호인지를 검사

                  > 쌍이 맞으면 스택에서 pop

                  > 쌍이 맞지 않으면 false 반환

- 모든 문자열을 검사한 후, 스택이 비어 있는지를 검사

> 비어 있으면 true 반환

> 그렇지 않으면 false 반환

 

#include <iostream>
#include <stack>

using namespace std;

bool paren_check(const string& s)
{
    stack<char> stk;
    
    for (char c : s){
        
        // 여는 괄호를 만나면 스택에 push
        if (c == '(' || c == '{' || c == '['){
            stk.push(c);
        }
        
        // 닫는 괄호를 만나면...
        else {
            
            // 스택이 비어 있으면 false 반환
            if (stk.empty()){
                return false;
            }
            
            // 스택의 top에 있는 문자가 현대 닫는 괄호와 쌍을 이루는 여는 괄호인지를 검사...
            if ((stk.top() == '(' && c == ')') || (stk.top() == '{' && c == '}') || (stk.top() == '[' && c == ']')){
                stk.pop();
            }
            else
                return false;
        }
    }
    // 모든 문자열을 검사한 후, 스택이 비어 있는지를 검사
    if (stk.empty())
        return true;
    else
        return false;
}

    
    
int main()
{
    // 올바른 괄호
    cout << paren_check("(){}[]") << endl;
    cout << paren_check("((((()))))") << endl;
    cout << paren_check("(){[()]}") << endl;
    
    // 올바르지 않은 괄호
    cout << paren_check("((({}))") << endl;
    cout << paren_check(")(") << endl;
    cout << paren_check("({)}") << endl;
}