Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 표현식의 괄호 균형 검사하기 – 스택(Stack) 활용 완벽 가이드

프로그래밍에서 문자열이나 수식을 다룰 때 괄호가 올바르게 짝을 이루고 있는지 확인해야 하는 경우가 자주 발생합니다. 이번 글에서는 C++을 사용하여 표현식 내의 괄호가 균형 잡혀 있는지(balanced) 검사하는 방법을 알아보겠습니다.

검사 대상이 되는 괄호는 소괄호 (), 중괄호 {}, 대괄호 [] 세 가지입니다. 예를 들어 다음과 같은 두 개의 문자열이 있다고 가정해 봅시다.

  • ()[(){()}] → 모든 괄호가 올바른 순서로 열리고 닫히므로 유효(valid)합니다.
  • {[}] → 여는 괄호와 닫는 괄호의 짝이 서로 맞지 않으므로 유효하지 않습니다(invalid).

문제 해결 접근 방법: 스택 활용

이 문제는 스택(Stack) 자료구조를 사용하면 간단하게 해결할 수 있습니다. 스택은 LIFO(Last In, First Out, 후입선출) 구조로 동작하기 때문에, 가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다는 괄호의 성질과 완벽하게 일치합니다.

알고리즘 단계

  1. 표현식을 처음부터 끝까지 한 문자씩 순회(traverse)합니다.
    • 현재 문자가 여는 괄호((, {, [)라면 스택에 push 합니다.
    • 현재 문자가 닫는 괄호(), }, ])라면 스택에서 pop 하여, 꺼낸 괄호가 현재 닫는 괄호와 짝이 맞는 여는 괄호인지 확인합니다. 짝이 맞으면 계속 진행하고, 그렇지 않으면 균형이 깨진 것으로 판단합니다.
  2. 문자열 순회가 끝난 후에도 스택에 여는 괄호가 남아 있다면, 닫히지 않은 괄호가 존재한다는 의미이므로 균형 잡힌 표현식이 아닙니다.

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++) {
        // 여는 괄호라면 스택에 push
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            stk.push(exp[i]);
            continue;
        }
        // 닫는 괄호인데 스택이 비어 있으면 균형 X
        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;
        }
    }
    // 순회 종료 후 스택이 비어 있어야 균형 O
    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

코드 설명 및 시간 복잡도

위 코드의 동작 흐름을 정리하면 다음과 같습니다.

  • 여는 괄호 처리: (, [, {를 만나면 스택에 저장하고 다음 문자로 넘어갑니다.
  • 닫는 괄호 처리: 닫는 괄호를 만났을 때 스택이 비어 있다면 짝이 없는 닫는 괄호이므로 즉시 false를 반환합니다.
  • 짝 검사: 스택의 top에 있는 괄호를 꺼내(pop) 현재 닫는 괄호와 종류가 일치하는지 확인합니다. 예를 들어 )에는 반드시 (가 대응되어야 하며, {나 [가 나오면 잘못된 짝이므로 false를 반환합니다.
  • 최종 확인: 모든 문자를 처리한 뒤 스택이 비어 있으면 모든 괄호가 정상적으로 닫힌 것이므로 true를 반환합니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 최악의 경우 모든 문자가 여는 괄호일 때 스택에 저장되므로 공간 복잡도 역시 O(n)입니다.

마무리

스택을 활용한 괄호 균형 검사는 컴파일러의 문법 분석기(parser), 코드 에디터의 자동 들여쓰기, 수식 계산기 등 다양한 곳에서 실제로 활용되는 기본적이면서도 중요한 알고리즘입니다. 위 예제 코드를 응용하면 중첩된 태그 검증이나 유효한 괄호 쌍의 개수 세기 등의 확장 문제도 손쉽게 해결할 수 있습니다.