Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++ 교체가 포함된 균형 표현식

<시간/>

균형 잡힌 괄호 표현은 모든 종류의 괄호 쌍을 올바른 순서로 함께 포함하는 표현입니다. 이는 모든 여는 괄호에 대해 올바른 순서로 닫는 괄호가 있음을 의미합니다(예:{ }.

).

개념을 더 잘 이해하기 위해 몇 가지 예를 들어보겠습니다. −

표현 - {([][]{})({}[]{})}

출력 - 균형

설명 - 여는 괄호마다 닫는 괄호가 있음을 알 수 있습니다. 여는 괄호와 닫는 괄호 사이에 있는 모든 괄호는 쌍으로 표시됩니다.

출력 - 균형이 아님

설명 - 표현식을 불균형하게 만드는 정렬되지 않은 괄호 쌍이 있습니다.

대체로 표현 균형이라고 하는 이 문제에서 , '{' , '}' , '[' , ']' , '(' , ')' 대괄호의 표현을 포함하는 문자열이 제공됩니다. 대괄호가 누락되어 "*"가 대신 배치되는 곳이 있습니다. 그리고 모든 별표 기호를 적절한 괄호로 대체할 때 주어진 표현식이 유효한 표현식이 될 수 있는지 날씨를 확인해야 합니다.

예

입력 - 특급 ="{[*(*)]}"

출력 - 표현이 균형을 이룰 수 있음

설명 − 교체해야 하는 두 가지 기호가 있습니다. 그리고 교체 시 {[(())]}

가 됩니다.

입력 − exp ="[(*){}{{}}]"

출력 - 표현이 균형을 이룰 수 없음

설명 − 교체해야 하는 기호가 하나 있습니다. 그리고 *를 대괄호로 대체하면 표현의 균형을 맞출 수 없습니다.

이제 문제에 대한 명확한 이해가 있으므로 이 문제에 대한 솔루션을 생성할 수 있습니다. 주어진 괄호 식이 균형을 이루는지 여부를 확인하기 위해 스택 데이터 구조를 사용하여 작업을 수행합니다.

이 작업을 수행하기 위해 수행되는 작업은 -

  • 문자열 표현식의 모든 요소를 ​​순회하고 −

  • 여는 괄호가 '{' , '[' , '(' , 스택에 있는 요소를 푸시합니다.

  • 식에서 닫는 대괄호(예:'}' , ']' , ')'가 있는 경우. 스택의 맨 위에 있는 요소를 팝하고 이것이 발견된 닫는 대괄호와 일치하는 개구부인지 확인합니다.

    • 두 괄호가 모두 일치하면 표현식의 다음 요소로 이동합니다(1단계).

    • 두 괄호가 모두 일치하지 않으면 표현식이 균형이 맞지 않습니다.

  • 여는 대괄호와 닫는 대괄호가 될 수 있는 표현식에 *가 있는 경우. 그럼

    • 먼저 여는 대괄호로 처리하고 스택으로 밀어넣고 다음 요소에 대한 재귀 호출을 사용하여 일치하는 닫는 대괄호를 찾습니다. 이로 인해 실패하면 다음 단계를 따르십시오.

    • 닫는 대괄호로 처리하고 스택 상단과 일치해야 하며 스택 상단을 팝업해야 합니다.

    • *의 종가가 시가와 균형이 맞지 않는 시가 수익률과 일치하지 않습니다.

  • 결과에 따라 명세서를 인쇄하십시오.

예시

이 솔루션을 기반으로 프로그램을 만들어 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
   if ((a == '{' &amp; b == '}') || (a == '[' &amp; b == ']') || (a == '(' &amp; b == ')') || a == '*')
      return 1;
   return 0;
}
int isBalancedexpression(string s, stack<char> ele, int ind){
   if (ind == s.length())
      return ele.empty();
   char topEle;
   int res;
   if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
      ele.push(s[ind]);
      return isBalancedexpression(s, ele, ind + 1);
   }
   else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
      if (ele.empty())
         return 0;
      topEle = ele.top();
      ele.pop();
      if (!isMatching(topEle, s[ind]))
         return 0;
      return isBalancedexpression(s, ele, ind + 1);
   }
   else if (s[ind] == '*') {
      stack<char> tmp = ele;
      tmp.push(s[ind]);
      res = isBalancedexpression(s, tmp, ind + 1);
      if (res)
         return 1;
      if (ele.empty())
         return 0;
      ele.pop();
      return isBalancedexpression(s, ele, ind + 1);
   }
}
int main(){
   string s = "{[*(*)]}";
   stack ele;
   if (isBalancedexpression(s, ele, 0))
      cout << "Balanced";
   else
      cout << "Not Balanced";
   return 0;
}

출력

Balanced