프로그래밍에서 문자열에 포함된 괄호가 서로 짝이 맞게 열리고 닫혔는지 확인하는 문제는 매우 자주 등장하는 고전적인 알고리즘 문제입니다. 이번 글에서는 C++의 스택(Stack) 자료구조를 활용하여 주어진 표현식의 괄호가 균형 잡혀 있는지(balanced) 판별하는 방법을 알아보겠습니다.
문제 정의
하나의 표현식(expression)이 주어졌을 때, 그 안에 포함된 괄호들이 올바르게 짝지어져 있는지 검사해야 합니다. 여기서 다루는 괄호의 종류는 소괄호 (), 중괄호 {}, 대괄호 [] 세 가지입니다.
예를 들어 다음과 같은 두 개의 문자열이 있다고 가정해 봅시다.
"()[(){()}]"→ 모든 괄호가 올바른 순서로 열리고 닫히므로 유효(valid)합니다."{[}]"→ 중괄호와 대괄호가 교차되어 닫히므로 유효하지 않습니다(invalid).
해결 접근 방법: 스택 활용
이 문제는 스택의 LIFO(Last In, First Out) 특성을 이용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 표현식 순회: 문자열의 처음부터 끝까지 한 글자씩 탐색합니다.
- 현재 문자가 여는 괄호(
(,{,[)라면 스택에 push합니다. - 현재 문자가 닫는 괄호(
),},])라면 스택에서 pop한 뒤, 방금 꺼낸 괄호가 현재 닫는 괄호와 짝이 맞는 여는 괄호인지 확인합니다. 짝이 맞으면 계속 진행하고, 맞지 않으면 즉시 균형이 깨진 것으로 판단합니다.
- 현재 문자가 여는 괄호(
- 최종 검사: 문자열을 모두 순회한 후에도 스택에 여는 괄호가 남아 있다면, 닫히지 않은 괄호가 존재한다는 의미이므로 균형이 맞지 않습니다. 스택이 비어 있어야만 유효한 표현식입니다.
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;
}
// 닫는 괄호인데 스택이 비어 있다면 균형이 깨짐
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) — 최악의 경우(모든 문자가 여는 괄호인 경우) 모든 문자를 스택에 저장해야 할 수 있습니다.
마무리
스택을 활용한 괄호 균형 검사는 컴파일러의 구문 분석기(syntax parser), 코드 에디터의 자동 들여쓰기 검사, 수식 계산기 등 다양한 실무 환경에서 응용되는 기본기입니다. 위 코드를 변형하면 어느 위치에서 균형이 깨졌는지 오류 지점을 보고하거나, 여러 종류의 구분자를 추가로 처리하는 확장도 손쉽게 구현할 수 있습니다.