C++로 유효한 괄호 문자열 판별하기: 스택을 활용한 균형 검사

어떤 수식(표현식)이 주어졌을 때, 그 안의 괄호가 서로 균형 잡혀 있는지(balanced) 확인해야 하는 경우가 있습니다. 검사 대상이 되는 괄호의 종류는 (), {}, [] 세 가지입니다.

예를 들어 두 개의 문자열이 있다고 가정해 보겠습니다.

• "()[(){()}]" → 모든 괄호가 올바른 순서로 짝을 이루므로 유효(valid)합니다.
• "{[}]" → 짝이 맞지 않는 괄호가 존재하므로 유효하지 않습니다(invalid).

문제 해결 접근 방법

이 문제는 스택(Stack) 자료구조를 이용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

1. 수식의 끝에 도달할 때까지 문자를 하나씩 순회(traverse)합니다.
   • 현재 문자가 여는 괄호((, {, [)라면 스택에 push합니다.
   • 현재 문자가 닫는 괄호(), }, ])라면 스택에서 pop합니다.
   • pop된 괄호가 현재 닫는 괄호와 짝을 이루는 여는 괄호인지 확인합니다. 짝이 맞으면 계속 진행하고, 그렇지 않다면 균형이 깨진 것입니다.
2. 문자열 순회가 끝난 후에도 스택에 여는 괄호가 남아 있다면, 닫히지 않은 괄호가 존재한다는 뜻이므로 균형 잡힌 문자열이 아닙니다.

C++ 구현 예제

아래 코드는 위 알고리즘을 C++로 구현한 것입니다.

#include <iostream>
#include <stack>
using namespace std;
bool isBalancedExp(string exp) {
    stack<char> stk;
    char x;
    for (int i=0; i<exp.length(); i++) {
        if (exp[i]=='('||exp[i]=='['||exp[i]=='{') {
            stk.push(exp[i]);
            continue;
        }
        if (stk.empty())
            return false;
        switch (exp[i]) {
        case ')':
            x = stk.top();
            stk.pop();
            if (x=='{' || x=='[')
                return false;
            break;
        case '}':
            x = stk.top();
            stk.pop();
            if (x=='(' || x=='[')
                return false;
            break;
        case ']':
            x = stk.top();
            stk.pop();
            if (x =='(' || x == '{')
                return false;
            break;
        }
    }
    return (stk.empty());
}
int main() {
    string expresion = "()[(){()}]";
    if (isBalancedExp(expresion))
        cout << "This is Balanced Expression";
    else
        cout << "This is Not Balanced Expression";
}

입력

"()[(){()}]"

출력

This is Balanced Expression

동작 원리 정리

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 최악의 경우 O(n)입니다. 여는 괄호를 만나면 스택에 저장하고, 닫는 괄호를 만나면 가장 최근에 들어간 여는 괄호와 짝이 맞는지 비교하는 LIFO(Last In, First Out) 특성 덕분에 중첩된 괄호 구조도 정확하게 검사할 수 있습니다. 또한 닫는 괄호가 나왔는데 스택이 비어 있다면 짝이 없는 닫는 괄호이므로 즉시 false를 반환하여 잘못된 입력을 빠르게 걸러냅니다.