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