개요
이 글에서는 스택(Stack) 자료구조를 활용하여 괄호의 균형 여부를 확인하는 방법을 살펴봅니다. 단순히 여는 괄호와 닫는 괄호의 개수만 세는 것이 아니라, 각 괄호가 올바른 순서로 짝을 이루고 있는지까지 검사합니다. 예를 들어 표현식 "[{}(){()}]"는 올바른 반면, "{[}]"는 닫는 괄호의 순서가 어긋나므로 올바르지 않습니다.
입력: 괄호가 포함된 표현식 "{()}[]"
출력: 균형이 맞습니다(Balanced)
알고리즘
괄호 균형 검사는 다음과 같은 절차로 진행됩니다.
- 1단계: 괄호를 저장할 스택을 정의합니다.
- 2단계: 표현식을 왼쪽에서 오른쪽으로 순회하며 다음을 수행합니다.
- 2.1단계: 문자가 여는 괄호 '(', '{', '[' 중 하나라면 스택에 푸시(push)합니다.
- 2.2단계: 문자가 닫는 괄호 ')', '}', ']' 중 하나라면 스택에서 팝(pop)하고, 팝된 문자가 해당 닫는 괄호와 짝이 맞으면 계속 진행하고, 그렇지 않으면 균형이 맞지 않는 것으로 판정합니다.
- 3단계: 순회가 끝난 후에도 스택에 여는 괄호가 남아 있다면 균형이 맞지 않는 것입니다.
예제 코드
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include<iostream>
#include<stack>
using namespace std;
bool isBalanced(string expr) {
stack<char> s;
char ch;
for (int i=0; i<expr.length(); i++) { // 표현식의 각 문자에 대해 조건 검사
if (expr[i]=='('||expr[i]=='['||expr[i]=='{') { // 여는 괄호이면 스택에 푸시
s.push(expr[i]);
continue;
}
if (s.empty()) // 여는 괄호가 아닌데 스택이 비어 있으면 균형이 맞지 않음
return false;
switch (expr[i]) {
case ')': // 닫는 소괄호: 팝 후 중괄호나 대괄호가 나오면 실패
ch = s.top();
s.pop();
if (ch=='{' || ch=='[')
return false;
break;
case '}': // 닫는 중괄호: 팝 후 소괄호나 대괄호가 나오면 실패
ch = s.top();
s.pop();
if (ch=='(' || ch=='[')
return false;
break;
case ']': // 닫는 대괄호: 팝 후 소괄호나 중괄호가 나오면 실패
ch = s.top();
s.pop();
if (ch =='(' || ch == '{')
return false;
break;
}
}
return (s.empty()); // 모든 처리 후 스택이 비어 있으면 true 반환
}
main() {
string expr = "[{}(){()}]";
if (isBalanced(expr))
cout << "Balanced";
else
cout << "Not Balanced";
}
코드 설명
isBalanced 함수는 문자열을 한 글자씩 확인하며 여는 괄호를 만나면 스택에 쌓고, 닫는 괄호를 만나면 스택 최상단(top)의 문자를 꺼내 짝이 맞는지 비교합니다. 닫는 괄호가 나왔는데 스택이 비어 있다면 짝이 될 여는 괄호가 없다는 의미이므로 즉시 false를 반환합니다. 또한 짝이 맞더라도 괄호 종류가 일치하지 않으면(예: '(' 에 대해 '}' 가 나오는 경우) 역시 실패로 처리합니다. 모든 문자를 처리한 뒤 스택이 완전히 비어 있어야만 균형 잡힌 표현식으로 판정하며, 이렇게 하면 여는 괄호가 남는 경우도 자동으로 걸러집니다.
실행 결과
Balanced