괄호와 스택

문제중에 괄호 관련된 문제가 종종 나온다.

 

아마도 개발하다보면 괄호가 부족해서 오류가 나오는 경우가 종종 발생해서 그런가보다.

 

간단한 문제로는 괄호가 잘 닫혔는지 확인하는 문제가 나오고, 더 나아가서는 특정 패턴으로 불완전한 괄호를 완성시키는 문제가 나온다.

 

이런 괄호가 정상적으로 매칭되어있는지 확인할 때, 스택을 사용한다.

 

여는 괄호가 있으면 닫힌 괄호가 있을테니 각각의 괄호를 카운트해서 숫자가 같으면 맞다고 판단하는 방법을 쓰면 갯수는 맞지만, 괄호의 순서가 다른 경우에는 오답이 된다.

 

그래서 스택을 써서 괄호가 여는 괄호일때는 스택에 넣고, 닫힌 괄호일때는 여는 괄호를 빼내는 방법을 사용한다.

 

bool complete(string u)
{
    stack<char> s;
    
    for(int i=0; i<u.length(); i++)
    {
        if(u[i] == '(')
        {
            s.push('(');
        }
        else
        {
            if(!s.empty())
            {
                if(s.top() == '(')
                {
                    s.pop();
                }
            }
            else
            {
                return false;
            }
        }
    }
    if(s.empty()) return true;
    else return false;
}

 

다른 방식도 있겠지만, 이 방식을 사용하는게 스택 함수 연습도 되니 좋다.