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