표현식이 있다고 가정합니다. 표현식에는 일부 괄호가 있습니다. 괄호의 균형이 맞는지 확인해야 합니다. 괄호의 순서는 (), {}, []입니다. 두 개의 문자열이 있다고 가정합니다. "()[(){()}]"는 유효하지만 "{[}]"는 유효하지 않습니다.
작업은 간단합니다. 우리는 이것을 하기 위해 스택을 사용할 것입니다. 솔루션을 얻으려면 다음 단계를 따라야 합니다 −
- 소진될 때까지 표현식을 탐색합니다.
- 현재 문자가 (, { 또는 [와 같은 여는 대괄호인 경우 스택에 푸시합니다.
- 현재 문자가 ), } 또는 ]와 같은 닫는 대괄호이면 스택에서 팝하고 팝된 대괄호가 현재 문자의 시작 대괄호에 해당하는지 확인하면 문제가 없고 그렇지 않으면 균형이 맞지 않습니다.
- 문자열이 소진된 후 스택에 시작 브래킷이 남아 있으면 문자열의 균형이 맞지 않습니다.
예시
#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